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)

Full work available at URL https://doi.org/10.1016/0166-218X(84)90019-2

zbMATH Keywords

connected components of an undirected graphspeed-upsynchronized parallel algorithm

Mathematics Subject Classification ID

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

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

• 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
• scientific article; zbMATH DE number 3576688 (Why is no real title available?)
• 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

(17)

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

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)