On the shortest spanning subtree of a graph and the traveling salesman problem

By Joseph B. Kruskal. 1956

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

GADMM: Fast and Communication Efficient Framework for Distributed Machine Learning (2019, methodology): “Even though an approach like spanning tree can be used to create such a graph (Tarjan, 1976; Kruskal, 1956), coming up with the most communication eﬃcient graph is a NP complete problem (being a generalization of traveling salesman problem) and is beyond the scope of this paper.”
Quantifying Generalization in Reinforcement Learning (2018, neutral): “Mazes are generated using Kruskal’s algorithm (Kruskal, 1956).”
Leveraging Procedural Generation to Benchmark Reinforcement Learning (2019, methodology): “Procedural generation controls the level layout by generating mazes using Kruskal’s algorithm (Kruskal, 1956).”
Spanning trees and optimization problems (2004, background): “Boca Raton London New York Washington, D.C. Chapter 2”
A unified heuristic for a large class of Vehicle Routing Problems with Backhauls (2006, methodology): “A heuristic for finding such a partition can be constructed by modifying Kruskal’s algorithm [24] for the minimum spanning tree problem.”
A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search (2021, methodology): “As the scale, cluster, and standard deviation increase, the advantages of RNG- and MSTbased algorithms over KNNG- and DG-based algorithms become more and more obvious.”
Global Pose Estimation with an Attention-Based Recurrent Network (2018, methodology): “For the 3D Environment, random maze designs are generated using the Kruskal’s algorithm [24], and the environment is created using the ViZDoom API [21].”
A Multiobjective Heuristic for Reconfiguration of the Electrical Radial Network (2013, methodology): “They guarantee the radial condition by using Kruskal’s algorithm [25].”
The Algorithm Design Manual (2020, background): “Kruskal’s algorithm is an alternative approach to finding minimum spanning trees that proves more efficient on sparse graphs.”
Assessing the Calibration of High-Dimensional Ensemble Forecasts Using Rank Histograms (2013, methodology): “The 79 spanning tree with the smallest length is then the minimum spanning tree (Kruskal, 1956); it may 80 e.”
Simulated brain tumor growth dynamics using a three-dimensional cellular automaton. (2000, unknown): “( 2000 Academic Press”
Multivariate generalizations of the Wald--Wolfowitz and Smirnov two-sample tests (1979, methodology): “This is amplified by the following two theorems from Prim (1957) [see also Kruskal (1956)].”