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.