无向图的边极大匹配并行算法及其应用<sup>*</sup>

马　军; 岩间一雄; 顾谦平

引用本文:	马　军,岩间一雄,顾谦平.无向图的边极大匹配并行算法及其应用^*.软件学报,1999,10(1):107-110

【打印本页】【下载PDF全文】【查看/发表评论】【EndNote】【RefMan】【BibTex】

←前一篇|后一篇→

过刊浏览高级检索

本文已被：浏览 4529次下载 4940次	码上扫一扫！
分享到：微信更多字体:加大+\|默认\|缩小-
无向图的边极大匹配并行算法及其应用^*
马　军¹, 岩间一雄², 顾谦平³
1.山东大学计算机科学系,济南,250100;2.京都大学计算机科学系,日本京都市;3.会津大学软件系,日本若松市

摘要:

在EREW PRAM(exclusive-read and exclusive-write parallel random access machine)并行计算模型上,对范围很广的一类无向图的边极大匹配问题,给出时间复杂性为O(logn),使用O((n+m)/logn)处理器的最佳、高速并行算法.

关键词: 并行图算法,边极大匹配.

DOI：

分类号:

基金项目:本文研究得到国家自然科学基金、国家863高科技项目基金、山东省自然科学基金和山东大学跨世纪人才基金资助.

A Parallel Maximal Matching Algorithm for Undirected Graphs with Applications

MA Jun,IWAMA Kazuo,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).

Key words: Parallel graph algorithms, maximal matching.

引用本文: