Backwards analysis of the Karger-Klein-Tarjan algorithm for minimum spanning trees

DOI10.1016/S0020-0190(98)00129-XzbMath1339.68309MaRDI QIDQ293385

Timothy M. Chan

Publication date: 9 June 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: http://www.sciencedirect.com/science/article/pii/S002001909800129X?np=y

zbMATH Keywords

randomized algorithmsminimum spanning treesbackwards analysis

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Related Items (1)

The saga of minimum spanning trees

Cites Work

• Unnamed Item
• Unnamed Item
• Random sampling and greedy sparsification for matroid optimization problems
• A randomized linear-time algorithm to find minimum spanning trees
• A combinatorial bound for linear programming and related problems

This page was built for publication: Backwards analysis of the Karger-Klein-Tarjan algorithm for minimum spanning trees