scientific article; zbMATH DE number 437524

MaRDI QIDQ3140396zbMATH OpenFDO

Authors Ka Wong Chong, Tak-Wah Lam

Publication date 15 December 1993

zbMATH Keywords

undirected graphconnected componentsEREW PRAM

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Recommendations

• Finding Connected Components in O(log n log log n) Time on the EREW PRAM
• Fast Connected Components Algorithms for the EREW PRAM
• 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
• An optimal randomised logarithmic time connectivity algorithm for the EREW PRAM

Cited in

(11)

• Finding Connected Components in O(log n log log n) Time on the EREW PRAM
• Hammock-on-ears decomposition: A technique for the efficient parallel solution of shortest paths and other problems
• An optimal EREW PRAM algorithm for minimum spanning tree verification
• An unambiguous class possessing a complete set
• Connected components in \(O(\log^{3/2}n)\) parallel time for the CREW PRAM
• Graph connectivity in log steps using label propagation
• Hammock-on-ears decomposition: a technique for the efficient parallel solution of shortest paths and other problems
• Optimal parallel algorithm for Brooks' colouring bounded degree graphs in logarithmic time on EREW PRAM
• Efficient enumeration of all minimal separators in a graph
• Static and dynamic parallel computation of connected components
• Optimal algorithms for the single and multiple vertex updating problems of a minimum spanning tree

This page was built for publication:

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