A randomized linear-time algorithm for finding minimum spanning trees
From MaRDI portal
Publication:2817593
DOI10.1145/195058.195084zbMath1344.68277OpenAlexW2011824743MaRDI QIDQ2817593
Philip N. Klein, Robert Endre Tarjan
Publication date: 1 September 2016
Published in: Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/195058.195084
Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Signed and weighted graphs (05C22)
Related Items
Optimal parallel verification of minimum spanning trees in logarithmic time ⋮ Approximate single linkage cluster analysis of large data sets in high-dimensional spaces ⋮ Efficient approximate solution of sparse linear systems ⋮ Spanning trees and shortest paths in Monge graphs ⋮ A simpler minimum spanning tree verification algorithm ⋮ Random sampling and greedy sparsification for matroid optimization problems
This page was built for publication: A randomized linear-time algorithm for finding minimum spanning trees
