A randomized linear-time algorithm to find minimum spanning trees
From MaRDI portal
Publication:4369866
DOI10.1145/201019.201022zbMath0886.68079OpenAlexW2138304862WikidataQ55871136 ScholiaQ55871136MaRDI QIDQ4369866
Philip N. Klein, David R. Karger, Robert Endre Tarjan
Publication date: 2 February 1998
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/201019.201022
Related Items
Population-driven urban road evolution dynamic model ⋮ Randomized OBDD-based graph algorithms ⋮ Backwards analysis of the Karger-Klein-Tarjan algorithm for minimum spanning trees ⋮ A novel dynamic minimum spanning tree based clustering method for image mining ⋮ A 2k-vertex Kernel for Maximum Internal Spanning Tree ⋮ Using sparsification for parametric minimum spanning tree problems ⋮ Proof labeling schemes ⋮ Cuttings for disks and axis-aligned rectangles in three-space ⋮ A simpler minimum spanning tree verification algorithm ⋮ Minimum spanning paths and Hausdorff distance in finite ultrametric spaces ⋮ An Optimal Parallel Algorithm for Minimum Spanning Trees in Planar Graphs ⋮ A new approach for the multiobjective minimum spanning tree ⋮ Tight bounds for distributed minimum-weight spanning tree verification ⋮ Linear-time algorithms for parametric minimum spanning tree problems on planar graphs ⋮ Minimum shared‐power edge cut ⋮ Decomposable multi-parameter matroid optimization problems. ⋮ Relation-algebraic verification of Borůvka's minimum spanning tree algorithm ⋮ Faster cut sparsification of weighted graphs ⋮ On symbolic OBDD-based algorithms for the minimum spanning tree problem ⋮ Distributed verification of minimum spanning trees ⋮ Amplification and Derandomization without Slowdown ⋮ The saga of minimum spanning trees ⋮ Absorbing random walks and the NAE2SAT problem ⋮ Single-Source Bottleneck Path Algorithm Faster than Sorting for Sparse Graphs. ⋮ A stronger lower bound on parametric minimum spanning trees ⋮ Finding real-valued single-source shortest paths in o(n 3) expected time ⋮ Resistant estimation of multivariate location using minimum spanning trees ⋮ On Cartesian trees and range minimum queries ⋮ Dynamic bottleneck optimization for \(k\)-edge and 2-vertex connectivity ⋮ Well-separated pair decomposition in linear time? ⋮ Sensitivity analysis for shortest path problems and maximum capacity path problems in undirected graphs ⋮ Finding the \(k\) most vital edges with respect to minimum spanning trees for fixed \(k\) ⋮ Minimum-weight spanning tree algorithms. A survey and empirical study ⋮ Finding multi-objective supported efficient spanning trees ⋮ UNSUPERVISED LEARNING BASED DISTRIBUTED DETECTION OF GLOBAL ANOMALIES ⋮ Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree ⋮ CASCADING RANDOM WALKS ⋮ Random walks for selected Boolean implication and equivalence problems ⋮ Design and Engineering of External Memory Traversal Algorithms for General Graphs ⋮ On memoryless provers and insincere verifiers ⋮ Learning directed acyclic graph SPNs in sub-quadratic time ⋮ A selectable sloppy heap ⋮ Density-based O-Means clustering algorithm using minimum spanning tree ⋮ Random sampling and greedy sparsification for matroid optimization problems ⋮ A new algorithm for the minimum spanning tree verification problem ⋮ Optimal Algorithms for Geometric Centers and Depth ⋮ The expected complexity of Prim's minimum spanning tree algorithm
