Finding Minimum Spanning Trees

DOI10.1137/0205051zbMath0358.90069OpenAlexW2128865241WikidataQ56092059 ScholiaQ56092059MaRDI QIDQ4132283

David Cheriton, Robert Endre Tarjan

Publication date: 1976

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/a1fbe390aedc05a87e5903ba83978b57d883a298

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Numerical mathematical programming methods (65K05)

Related Items

Computing relative neighbourhood graphs in the plane, Efficient algorithms for finding minimum spanning trees in undirected and directed graphs, On-line updating of solutions to a class of matroid intersection problems, A data structure for bicategories, with application to speeding up an approximation algorithm, The 1-Steiner-Minimal-Tree problem in Minkowski-spaces, On the Steiner ratio in 3-space, Finding the k smallest spanning trees, Sorting helps for Voronoi diagrams, An Optimal Parallel Algorithm for Minimum Spanning Trees in Planar Graphs, A Low Arithmetic-Degree Algorithm for Computing Proximity Graphs, Steiner minimal trees in \(L^ 2_ p\), Linear-time algorithms for parametric minimum spanning tree problems on planar graphs, On the probabilistic min spanning tree problem, Ranking arborescences in O(Km log n) time, Consensus-based decision support model and fusion architecture for dynamic decision making, Decomposable multi-parameter matroid optimization problems., A fast algorithm for Steiner trees, Complexity of spanning tree problems: Part I, Finding minimal spanning trees in a Euclidean coordinate space, On symbolic OBDD-based algorithms for the minimum spanning tree problem, Minimum-sum dipolar spanning tree in \(\mathbb R^3\), On the relationship between the biconnectivity augmentation and traveling salesman problems, Minimal spanning trees and partial sorting, The saga of minimum spanning trees, The Steiner ratio of high-dimensional Banach--Minkowski spaces., A pointer-free data structure for merging heaps and min-max heaps, Minimal length tree networks on the unit sphere, Single-Source Bottleneck Path Algorithm Faster than Sorting for Sparse Graphs., Percolation on complex networks: theory and application, Three priority queue applications revisited, Proximity problems for points on a rectilinear plane with rectangular obstacles, There are planar graphs almost as good as the complete graphs and almost as cheap as minimum spanning trees, Finding the \(k\) smallest spanning trees, An in-depth empirical investigation of non-greedy approaches for the minimum spanning tree problem, Complexity of algorithm and operations on trees, A fast minimum spanning tree algorithm based on \(K\)-means, Risk-control approach for a bottleneck spanning tree problem with the total network reliability under uncertainty, An \(O(\log m)\) parallel algorithm for the minimum spanning tree problem, On sorting, heaps, and minimum spanning trees, Optimal chain partitions of trees, On the restricted 1-Steiner tree problem, A linear-size zero?one programming model for the minimum spanning tree problem in planar graphs, Weighted \({\mathcal A}\)-shape: A descriptor of the shape of a point set, Refined complexity analysis for heap operations, Fast reoptimization for the minimum spanning tree problem, Minimum-weight spanning tree algorithms. A survey and empirical study, The Min-Max Spanning Tree Problem and some extensions, Delay-constrained minimum shortest path trees and related problems, The minimum spanning tree problem on a planar graph, Delay-constrained minimum shortest path trees and related problems, Efficient parallel algorithms for graph problems, Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation, Linear-time algorithms for parametric minimum spanning tree problems on planar graphs, An improved algorithm for hierarchical clustering using strong components, The vertex degrees of minimum spanning trees, On the restricted \(k\)-Steiner tree problem, Stochastic bottleneck spanning tree problem, Computational experience with minimum spanning tree algorithms, On computing all north-east nearest neighbors in the \(L_ 1\) metric, The stochastic bottleneck linear programming problem, Linear verification for spanning trees, A parallel algorithm for generating multiple ordering spanning trees in undirected weighted graphs, Optimal vertex ordering of graphs, On recursive computation of minimum spanning trees for special partial graphs, A linear algorithm for analysis of minimum spanning and shortest-path trees of planar graphs