A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest
From MaRDI portal
Publication:4785625
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)
68R10: Graph theory (including graph drawing) in computer science
68Q85: Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Time-optimal construction of overlay networks, A fast minimum spanning tree algorithm based on \(K\)-means, On sorting, heaps, and minimum spanning trees, Combinatorial optimization in system configuration design, TAN classifiers based on decomposable distributions, Distributed verification of minimum spanning trees, Connectivity Oracles for Graphs Subject to Vertex Failures, An Optimal Parallel Algorithm for Minimum Spanning Trees in Planar Graphs