Finding Minimum Spanning Trees

DOI10.1137/0205051zbMATH Open0358.90069OpenAlexW2128865241WikidataQ56092059 ScholiaQ56092059MaRDI QIDQ4132283FDOQ4132283

David Cheriton, Robert E. 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

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

Cited In (66)

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

This page was built for publication: Finding Minimum Spanning Trees

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