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

DOI10.1016/S0020-0190(98)00129-XzbMATH Open1339.68309MaRDI QIDQ293385FDOQ293385

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

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

zbMATH Keywords

randomized algorithmsminimum spanning treesbackwards analysis

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• A combinatorial bound for linear programming and related problems
• Random sampling and greedy sparsification for matroid optimization problems
• Title not available (Why is that?)
• A randomized linear-time algorithm to find minimum spanning trees

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)