并行图论算法研究进展

在这篇综述文章中，我们将重点介绍并行图论处近年来的发展概况及主要成果，并给出一些可能的发展方向。具体内容包括：基于共享存储模型上的图搜索技术、连发支及最小生成树算法、增值并行图论算法、最短路径算法、极大独立集算法、极大匹配与最大匹配算法，图着色算法、求欧拉回路及哈密尔顿回路算法，图同构算法、图Ｋ连通算法以及最大流最小割算法等。

RESEARCH ADVANCES IN PARALLEL GRAPH ALGORITHMS

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.