首页 | 本学科首页   官方微博 | 高级检索  
     

无向图的边极大匹配并行算法及其应用*
引用本文:马 军,岩间一雄,顾谦平.无向图的边极大匹配并行算法及其应用*[J].软件学报,1999,10(1):107-110.
作者姓名:马 军  岩间一雄  顾谦平
作者单位:1. 山东大学计算机科学系,济南,250100
2. 京都大学计算机科学系,日本京都市
3. 会津大学软件系,日本若松市
基金项目:本文研究得到国家自然科学基金、国家863高科技项目基金、山东省自然科学基金和山东大学跨世纪人才基金资助.
摘    要:在EREW PRAM(exclusive-read and exclusive-write parallel random access machine)并行计算模型上,对范围很广的一类无向图的边极大匹配问题,给出时间复杂性为O(logn),使用O((n+m)/logn)处理器的最佳、高速并行算法.

关 键 词:并行图算法  边极大匹配
收稿时间:1997/3/27 0:00:00
修稿时间:1/5/1998 12:00:00 AM

A Parallel Maximal Matching Algorithm for Undirected Graphs with Applications
MA Jun,IWAMA Kazuo and GU Qian-ping.A Parallel Maximal Matching Algorithm for Undirected Graphs with Applications[J].Journal of Software,1999,10(1):107-110.
Authors:MA Jun  IWAMA Kazuo and GU Qian-ping
Abstract:A fast and optimal parallel maximal matching algorithm is proposed for a class of graphs. It runs in O(logn) time with O((n+m)/logn) processors on a EREW PRAM (exclusive-read and exclusive-write parallel random access machine).
Keywords:Parallel graph algorithms  maximal matching  
本文献已被 CNKI 维普 万方数据 等数据库收录!
点击此处可从《软件学报》浏览原始摘要信息
点击此处可从《软件学报》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号