An optimal parallel connectivity algorithm

DOI10.1016/0166-218X(84)90019-2zbMath0546.68044MaRDI QIDQ797997

Uzi Vishkin

Publication date: 1984

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

speed-upconnected components of an undirected graphsynchronized parallel algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Connectivity (05C40) Theory of operating systems (68N25)

Related Items

On efficient parallel strong orientation, Parallelism and the maximal path problem, Graph theory (algorithmic, algebraic, and metric problems), Approximate parallel scheduling. II: Applications to logarithmic-time optimal parallel graph algorithms, A parallel-design distributed-implementation (PDDI) general-purpose computer

Cites Work

• Unnamed Item
• Simulation of Parallel Random Access Machines by Circuits
• An Efficient Parallel Biconnectivity Algorithm
• Computing connected components on parallel computers
• Finding the maximum, merging, and sorting in a parallel computation model
• Ultracomputers
• An O(n2log n) parallel max-flow algorithm
• An O(logn) parallel connectivity algorithm
• The Parallel Evaluation of General Arithmetic Expressions
• Implementation of simultaneous memory address access in models that forbid it
• A unified approach to models of synchronous parallel machines