Randomized minimum spanning tree algorithms using exponentially fewer random bits

DOI10.1145/1328911.1328916zbMath1445.68344MaRDI QIDQ4962697

Vijaya Ramachandran, Seth Pettie

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 algorithms; random sampling; minimum spanning trees

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C85: Graph algorithms (graph-theoretic aspects)

68W20: Randomized algorithms