Efficient Parallel Algorithms for a Class of Graph Theoretic Problems

DOI10.1137/0213036zbMath0545.68060MaRDI QIDQ3335006

Francis Y. L. Chin, Yung Hyang Tsin

Publication date: 1984

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/10722/152217

zbMATH Keywords

parallel computation; analysis of algorithms; graph algorithms; efficient parallel algorithms; PRAM; SIMD machines; lowest common ancestors; fundamental cycles; biconnected components; directed spanning forests; bridge- connected components; separation vertices

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

Related Items

Parallel algorithms on interval graphs, An optimal parallel algorithm for computing cut vertices and blocks on interval graphs, On the Parallel Evaluation of Dwba Integrals, An optimal parallel algorithm to compute all cutvertices and blocks on permutation graphs, Distributed processing of graphs: Fundamental cycles algorithm, Optimal parallel algorithms for finding cut vertices and bridges of interval graphs, Parallel search algorithms for graphs and trees, A self-stabilizing algorithm for detecting fundamental cycles in a graph, An efficient distributed bridge-finding algorithm, Efficient minimum spanning tree algorithms on the reconfigurable mesh