并行图论算法研究进展

并行图论算法研究进展

’弓 q 2) C 第3 2卷 19 9 5年 9月 、、

维普资讯 doc.guandang.net

9期

1< i

、

。

v。 . 2 N 0 9 I 3 _ Se pt l 995

COM PUTER RES EARCH& DEVELOPM ENT

\

并行图论算法研究进展

墨究中心，合肥202)3 6 0堡_研沈鸿弋 o ?I。 (国衮葶机算石算中买系再 3 7 0 ' 摘要在这篇综述文章中，我们将重点介绍并行图论算法近年来的发展概况及主要成 果，并给出一些可能的发展方向。具体内容包括：于共享存储模型上的图搜索技术、基 连通分支及最小生成树算法、增值并行图论算法、最短路径算法、极走独立集算法、极大匹配与最走匹配算法、图着色算法、求欧拉回路及哈密尔顿回路算法、图同构算法图 k连通算法以及最大流最小割算法等关键词 P A, C算法， N R M N R C算法，图问题，算法复杂性分析。

S I

1引

言

并行图论算法的研究始于 7 o年代中期， 8年代中期已基本成熟。早期这方面工作主要集到 0 中在一些基本图论问题算法的研究上。后来，随着研究的深入，人们开始对复杂的图问题着手进 行研究，这方面典型的例子如图的最大匹配等。有关这一领域的早期成果，Qun in等人 给予了很好的概述。文献 E 3 8 z对 9年以前的成果作了系统的总结。1 9 9 1年 Vih iE对一些基本图问题 s kn3 3并行算法给予了很好的小结。除外，Kap等人Ⅲ的文章也值得一读。由于图论问题的多样性以及 r

这一领域的迅速发展，在这篇综述文章中，我们只能概括介绍一些典型问题研究的新进展以及一 些可能的生长点。

并行图论算法的研究基本上可分为两大类；一类着重研究一些基本图问题，如无向图的连通

分支，向图的可达性，连通分支，有强最小生成树，和深度 (度)宽优先搜索等；另一类则研究比较复杂的图问题，如最大基数 (加权)配，图着色，大流最小割等在其后各节中，匹最我们将具体介绍一些典型图论问题的并行算法。假定 G( E)有向或无向图，I I,I—I,且除非另有 V,是 V=n EI T I 说明，所有对数均以 2为底。

2并行计算模型及复杂性分类 随着最近十几年商业化的并行计算机的}现， b并行处理进入了前所未有的繁荣期。因为绝大 本文于] 9年儿月收到。 94本文得到高校博士点基盘赍助。国盅 . 9 1脒 1 6年毕业于西安交通大学 为中国科技大学教授，现 博士导师，算机系系主任 .主要研究领域为并行算{并行分布计算、能计算等。粱堆发，18计岳、智 9 4年毕业于武祝大学计算机系， 99 1 8年获中国科技大学碗士学位，同年续读中国科技大学 P I学位， 9 1在美国 u H3 19年 o Mi ui￣ ssCt进行合 f￣o t K na i— y鹚， 9 2毕业于 18年

作研究 .现在 A s ai al a U i.继续读 p I u t l nN t n[ nv r a o r _ D学位 .主要研究领域为并行及分布式圈论算法等 .沈

北京钢铁学院， 9 7获中国科技大学硬士学位，同年续读中国科技大学 P D学位，1 9年获芬兰 Ab k dmi nv博士 18年 H 91 oA ae i U学位 现为 A s a a r f u t nG i t rv副教授， M及 I E rL i￣ hU 6 AC E E会员，主要研究领域为并行算法 并行分布计算等。

doc.guandang.net