A Simpler Parallel Algorithm for Graph Connectivity

DOI10.1006/jagm.1994.1009zbMath0797.68071OpenAlexW1976398917MaRDI QIDQ4285909

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

zbMATH Keywords

connected componentsgraph connectivityundirected graphexpander graphsCRCW 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)

Related Items (3)

A faster parallel algorithm for \(k\)-connectivity ⋮ Optimal parallel algorithm for Brooks' colouring bounded degree graphs in logarithmic time on EREW PRAM ⋮ Graph Connectivity in Log Steps Using Label Propagation

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