Randomized minimum spanning tree algorithms using exponentially fewer random bits

DOI10.1145/1328911.1328916zbMath1445.68344OpenAlexW1992273661MaRDI QIDQ4962697

Seth Pettie, Vijaya Ramachandran

Publication date: 5 November 2018

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1328911.1328916

zbMATH Keywords

graph algorithmsrandom samplingminimum spanning trees

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Related Items (1)

How long it takes for an ordinary node with an ordinary ID to output?

This page was built for publication: Randomized minimum spanning tree algorithms using exponentially fewer random bits