A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest

DOI10.1137/S0097539700371065zbMath1006.05053WikidataQ56077919 ScholiaQ56077919MaRDI QIDQ4785625

Vijaya Ramachandran, Seth Pettie

Publication date: 5 January 2003

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

parallel algorithmoptimal algorithmminimum spanning treeEREW PRAM

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (8)

An Optimal Parallel Algorithm for Minimum Spanning Trees in Planar Graphs ⋮ Time-optimal construction of overlay networks ⋮ Distributed verification of minimum spanning trees ⋮ A fast minimum spanning tree algorithm based on \(K\)-means ⋮ On sorting, heaps, and minimum spanning trees ⋮ TAN classifiers based on decomposable distributions ⋮ Connectivity Oracles for Graphs Subject to Vertex Failures ⋮ Combinatorial optimization in system configuration design

This page was built for publication: A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest