摘要
在这篇综述文章中，我们将重点介绍并行图论算法近年来的发展概况及主要成果，并给出一些可能的发展方向。具体内容包括：基于共享存储模型上的图搜索技术、连通分支及最小生成树算法、增值并行图论算法、最短路径算法、极大独立集算法、极大匹配与最大匹配算法、图着色算法、求欧拉回路及哈密尔顿回路算法、图同构算法、图ｋ连通算法以及最大流最小割算法等。
In this paper, we give a survey of the research advances in parallel graph algorithms in these years. These algorithms based on the shared memory computation model (PRAM) include searching graphs, computing connected components, finding minimum spanning trees, computing incremental graphs, finding shortest paths, constructing maximal independent set and maximal matching, coloring edges and vertex of graphs, finding Euler tour and Hamiltonian cycles,testing isomorphism and k-connectivity of graphs, computing maximum flows and minimum cuts,etc.
出处
《计算机研究与发展》
EI
CSCD
北大核心
1995年第9期1-16,共16页
Journal of Computer Research and Development
基金
高校博士点基金
关键词
并行图论
算法
图论
PRAM
NC algorithm
RNC algorithm
graph problem
analysis of algorithm complexity.
