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

DOI10.1016/S0020-0190(98)00129-XMaRDI QIDQ293385zbMATHFDO

Authors 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

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

Recommendations

• A randomized linear-time algorithm for finding minimum spanning trees (extended abstract)
• Randomized minimum spanning tree algorithms using exponentially fewer random bits
• A randomized linear-time algorithm to find minimum spanning trees
• An optimal minimum spanning tree algorithm
• scientific article; zbMATH DE number 1670813

Cites work

• scientific article; zbMATH DE number 431985 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• A combinatorial bound for linear programming and related problems
• A randomized linear-time algorithm to find minimum spanning trees
• Random sampling and greedy sparsification for matroid optimization problems

Cited in

(1)

• The saga of minimum spanning trees

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q293385)