A Simpler Parallel Algorithm for Graph Connectivity

DOI10.1006/JAGM.1994.1009zbMATH Open0797.68071OpenAlexW1976398917MaRDI QIDQ4285909FDOQ4285909

Authors: Yahiko Kambayashi, Kazuo Iwama 

Publication date: 19 October 1994

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jagm.1994.1009

Recommendations

• Parallel algorithms for finding connected components of a graph
• Connected components in \(O(\log^{3/2}n)\) parallel time for the CREW PRAM
• Fast Connected Components Algorithms for the EREW PRAM
• Finding Connected Components in O(log n log log n) Time on the EREW PRAM
• An efficient and fast parallel-connected component algorithm

zbMATH Keywords

expander graphsgraph connectivityundirected graphconnected componentsCRCW PRAM algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Connectivity (05C40) Distributed algorithms (68W15)

Cited In (7)

• Parallel algorithms for connectivity problems in graph theory
• An Efficient Parallel Biconnectivity Algorithm
• A faster parallel algorithm for \(k\)-connectivity
• Title not available (Why is that?)
• Graph connectivity in log steps using label propagation
• Optimal parallel algorithm for Brooks' colouring bounded degree graphs in logarithmic time on EREW PRAM
• A faster parallel connectivity algorithm on cographs

This page was built for publication: A Simpler Parallel Algorithm for Graph Connectivity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4285909)