Efficient Parallel Algorithms for a Class of Graph Theoretic Problems
From MaRDI portal
Publication:3335006
DOI10.1137/0213036zbMath0545.68060OpenAlexW2004090025MaRDI 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
parallel computationanalysis of algorithmsgraph algorithmsefficient parallel algorithmsPRAMSIMD machineslowest common ancestorsfundamental cyclesbiconnected componentsdirected spanning forestsbridge- connected componentsseparation vertices
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items
An O(log n) algorithm for parallel update of minimum spanning trees, An efficient distributed bridge-finding algorithm, On the parallel computation of the biconnected and strongly connected co-components of graphs, An efficient parallel algorithm for updating minimum spanning trees, Computing dominators in parallel, PARALLEL BLOCK-FINDING USING DISTANCE MATRICES, On the Parallel Evaluation of Dwba Integrals, Parallel algorithms on interval graphs, Efficient minimum spanning tree algorithms on the reconfigurable mesh, 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, Graph theory (algorithmic, algebraic, and metric problems), An optimal parallel algorithm to compute all cutvertices and blocks on permutation graphs, Optimal parallel algorithms on planar graphs, A self-stabilizing algorithm for detecting fundamental cycles in a graph, Approximate parallel scheduling. II: Applications to logarithmic-time optimal parallel graph algorithms, An optimal parallel algorithm for computing cut vertices and blocks on interval graphs, An optimal parallel processor bound in strong orientation of an undirected graph, A parallel algorithm for generating multiple ordering spanning trees in undirected weighted graphs
