Static and dynamic parallel computation of connected components

DOI10.1016/0020-0190(94)00016-6zbMath0803.68088OpenAlexW2053942345MaRDI QIDQ1322111

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 componentsparallel algorithmsundirected graphsparsificationtree data structureEREW modelwork-optimality

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• An O(log n) algorithm for parallel update of minimum spanning trees
• 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
• Optimal algorithms for the single and multiple vertex updating problems of a minimum spanning tree
• An efficient and fast parallel-connected component algorithm
• Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
• Efficient parallel algorithms for some graph problems
• An O(logn) parallel connectivity algorithm
• Sparsification—a technique for speeding up dynamic graph algorithms

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