On the History of the Minimum Spanning Tree Problem

DOI10.1109/MAHC.1985.10011zbMath0998.68003WikidataQ56077923 ScholiaQ56077923MaRDI QIDQ4779256

Pavol Hell, Ronald L. Graham

Publication date: 25 November 2002

Published in: IEEE Annals of the History of Computing (Search for Journal in Brave)

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) History of mathematics in the 20th century (01A60) History of operations research and mathematical programming (90-03) History of computer science (68-03)

Related Items (57)

Finding outbreak trees in networks with limited information ⋮ The scaling limits of the minimal spanning tree and invasion percolation in the plane ⋮ Balancing minimum spanning trees and multiple-source minimum routing cost spanning trees on metric graphs ⋮ Low-degree minimum spanning trees ⋮ A survey of constrained classification ⋮ Computing all efficient solutions of the biobjective minimum spanning tree problem ⋮ A new approach for the multiobjective minimum spanning tree ⋮ The reduction of computation times of upper and lower tolerances for selected combinatorial optimization problems ⋮ Fast heuristic algorithms for rectilinear Steiner trees ⋮ Tree index of uncertain graphs ⋮ Proof of a conjecture about minimum spanning tree cycle intersection ⋮ Integer Programming Formulations for Minimum Spanning Tree Interdiction ⋮ Tight bounds for distributed minimum-weight spanning tree verification ⋮ Steiner minimal trees in \(L^ 2_ p\) ⋮ An effective genetic algorithm approach to the quadratic minimum spanning tree problem ⋮ An effective two‐level solution approach for the prize‐collecting generalized minimum spanning tree problem by iterated local search ⋮ On conflict-free spanning tree: algorithms and complexity ⋮ Social distancing network creation ⋮ Geometric Network Creation Games ⋮ Models of random subtrees of a graph ⋮ Unnamed Item ⋮ Fractional interaction of financial agents in a stock market network ⋮ On some similarity of finite sets (and what we can say today about certain old problem) ⋮ The Impact of Cooperation in Bilateral Network Creation ⋮ Connected spatial networks over random points and a route-length statistic ⋮ The minimum-area spanning tree problem ⋮ A game-theoretical and cryptographical approach to crypto-cloud computing and its economical and financial aspects ⋮ Relation-algebraic verification of Borůvka's minimum spanning tree algorithm ⋮ Computing Euclidean maximum spanning trees ⋮ On symbolic OBDD-based algorithms for the minimum spanning tree problem ⋮ The saga of minimum spanning trees ⋮ Percolation on complex networks: theory and application ⋮ Multi-label Learning Through Minimum Spanning Tree-Based Subset Selection and Feature Extraction ⋮ Spanning-Tree Games. ⋮ Farthest neighbors, maximum spanning trees and related problems in higher dimensions ⋮ An in-depth empirical investigation of non-greedy approaches for the minimum spanning tree problem ⋮ A travelling salesman problem in the \(k\)-dimensional unit cube ⋮ Axiomatization of the Shapley value on minimum cost spanning tree games ⋮ The weighted arborescence constraint ⋮ Cost monotonicity, consistency and minimum cost spanning tree games ⋮ Connection situations under uncertainty and cost monotonic solutions ⋮ Critical random graphs and the structure of a minimum spanning tree ⋮ Minimum-weight spanning tree algorithms. A survey and empirical study ⋮ An algebraic framework for minimum spanning tree problems ⋮ Algorithms for Euclidean Degree Bounded Spanning Tree Problems ⋮ Degree bounded bottleneck spanning trees in three dimensions ⋮ The problem of the optimal biobjective spanning tree ⋮ Optimality conditions in preference-based spanning tree problems ⋮ A heuristic algorithm for the mini-max spanning forest problem ⋮ An Adaptive Minimum Spanning Tree Multielement Method for Uncertainty Quantification of Smooth and Discontinuous Responses ⋮ The vertex degrees of minimum spanning trees ⋮ Hierarchies in communities of UK stock market from the perspective of Brexit ⋮ On minimum- and maximum-weight minimum spanning trees with neighborhoods ⋮ A greedy algorithm for finding maximum spanning trees in infinite graphs ⋮ On Hop-Constrained Steiner Trees in Tree-Like Metrics ⋮ THE MINIMUM SPANNING TREE PROBLEM: Jarník's solution in historical and present context ⋮ Upper and lower bounding strategies for the generalized minimum spanning tree problem

This page was built for publication: On the History of the Minimum Spanning Tree Problem