What structural features make graph problems to have efficient parallel algorithms? Using outerplanar graphs, trapezoid graphs and in-tournament graphs as examples

This paper analyzes what structural features of graph problems allow effici ent parallel algorithms. We survey some parallel algorithms for typical pro blems on three kinds of graphs, outerplanar graphs, trapezoid graphs and in -tournament graphs. Our results on the shortest path problem, the longest p ath problem and the maximum flow problem on outerplanar graphs, the minimum -weight connected dominating set problem and the coloring problem on trapez oid graphs and Hamiltonian path and Hamiltonian cycle problem on in-tournam ent graphs are adopted as working examples.