Static and dynamic parallel computation of connected components

DOI10.1016/0020-0190(94)00016-6MaRDI QIDQ1322111zbMATH OpenOpenAlexFDO

Authors Paolo Ferragina

Publication date 5 May 1994

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(94)00016-6

zbMATH Keywords

connected componentsEREW modelparallel algorithmssparsificationtree data structureundirected graphwork-optimality

Mathematics Subject Classification ID

Connectivity (05C40) Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Recommendations

• An efficient and fast parallel-connected component algorithm
• Fast Connected Components Algorithms for the EREW PRAM
• scientific article; zbMATH DE number 3930349
• Connected components in \(O(\log^{3/2}n)\) parallel time for the CREW PRAM
• A new class of parallel algorithms for finding connected components on machines with bit-vector operations

Cites work

• An efficient and fast parallel-connected component algorithm
• An O(log n) algorithm for parallel update of minimum spanning trees
• An O(logn) parallel connectivity algorithm
• Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
• Efficient parallel algorithms for some graph problems
• scientific article; zbMATH DE number 437524 (Why is no real title available?)
• Optimal algorithms for the single and multiple vertex updating problems of a minimum spanning tree
• Parallel algorithms for computing maximal independent sets in trees and for updating minimum spanning trees
• Parallel algorithms for the connected components and minimal spanning tree problems
• Sparsification—a technique for speeding up dynamic graph algorithms

Cited in

(9)

• Dynamic connectivity for axis-parallel rectangles
• I/O- and CPU-optimal recognition of strongly connected components
• Work-efficient parallel union-find with applications to incremental graph connectivity
• Comparative study and proof of single-pass connected components algorithms
• An efficient and fast parallel-connected component algorithm
• Algebraic investigation of connected components
• scientific article; zbMATH DE number 5879017 (Why is no real title available?)
• Concurrent determination of connected components
• A study of connectivity on dynamic graphs: computing persistent connected components

This page was built for publication: Static and dynamic parallel computation of connected components

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