An optimal parallel connectivity algorithm

DOI10.1016/0166-218X(84)90019-2MaRDI QIDQ797997zbMATH OpenFDO

Authors 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)

Recommendations

• An efficient and fast parallel-connected component algorithm
• scientific article; zbMATH DE number 3930349
• An optimal parallel co-connectivity algorithm
• Approximate parallel scheduling. II: Applications to logarithmic-time optimal parallel graph algorithms
• An Efficient Parallel Biconnectivity Algorithm

Cites work

• scientific article; zbMATH DE number 3576688 (Why is no real title available?)
• A unified approach to models of synchronous parallel machines
• An Efficient Parallel Biconnectivity Algorithm
• An O(logn) parallel connectivity algorithm
• An O(n2log n) parallel max-flow algorithm
• Computing connected components on parallel computers
• Finding the maximum, merging, and sorting in a parallel computation model
• Implementation of simultaneous memory address access in models that forbid it
• Simulation of Parallel Random Access Machines by Circuits
• The Parallel Evaluation of General Arithmetic Expressions
• Ultracomputers

Cited in

(16)

• On efficient parallel strong orientation
• An optimal parallel algorithm to construct a deap
• Graph theory (algorithmic, algebraic, and metric problems)
• Parameterized algorithms for finding highly connected solution
• A faster parallel algorithm for \(k\)-connectivity
• An optimal parallel co-connectivity algorithm
• An Efficient Parallel Biconnectivity Algorithm
• Approximating unweighted connectivity problems in parallel
• Approximate parallel scheduling. II: Applications to logarithmic-time optimal parallel graph algorithms
• A parallel-design distributed-implementation (PDDI) general-purpose computer
• Parallelism and the maximal path problem
• An efficient and fast parallel-connected component algorithm
• Connection Scan Algorithm
• scientific article; zbMATH DE number 3860407 (Why is no real title available?)
• Parameterized algorithms for finding highly connected solution
• An 0(log n) parallel algorithm for strong connectivity augmentation problem

This page was built for publication: An optimal parallel connectivity algorithm

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