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

1956/02/01 by Joseph B. Kruskal · 90 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph theory and applications

paper · pdf · doi:10.1090/s0002-9939-1956-0078686-7

Abstract

7. A. Kurosh, Ringtheoretische Probleme die mit dem Burnsideschen Problem uber periodische Gruppen in Zussammenhang stehen, Bull. Acad. Sei. URSS, Ser. Math. vol. 5 (1941) pp. 233-240. 8. J. Levitzki, On the radical of a general ring, Bull. Amer. Math. Soc. vol. 49 (1943) pp. 462⁶6. 9. -, On three problems concerning nil rings, Bull. Amer. Math. Soc. vol. 49 (1943) pp. 913-919. 10. -, On the structure of algebraic algebras and related rings, Trans. Amer. Math. Soc. vol. 74 (1953) pp. 384-409.

Cited by

• De novo assembly of the <i>Aedes aegypti</i> genome using Hi-C yields chromosome-length scaffolds
• Polynomial-time algorithms for multimarginal optimal transport problems with structure
• A note on two problems in connexion with graphs
• Minimum Cuts and Sparsification in Hypergraphs
• Forcing a unique minimum spanning tree and a unique shortest path
• REST: Receding Horizon Explorative Steiner Tree for Zero-Shot Object-Goal Navigation
• Random Minimum Spanning Tree and Dense Graph Limits
• Beyond Semantics: The Unreasonable Effectiveness of Reasonless Intermediate Tokens
• An Analysis of Several Heuristics for the Traveling Salesman Problem
• A Simple, Faster Method for Kinetic Proximity Problems
• Adaptive Approximation of Functions with Discontinuities
• Active Neural Localization
• Global-Aware Edge Prioritization for Pose Graph Initialization
• Computing the Asymptotic Spectrum for Networks Representing Energy Landscapes using the Minimal Spanning Tree
• Leveraging Procedural Generation to Benchmark Reinforcement Learning
• Half-checking propagators
• Rank-based linkage I: triplet comparisons and oriented simplicial complexes
• Cell agglomeration strategy for cut cells in eXtended discontinuous Galerkin methods
• Algorithms to test open set condition for self-similar set related to P.V. numbers
• Oriented Minimum spanning tree looks like the Uniform spanning tree on the complete graph (at least locally)
• The global structure of locally chordal graphs
• Hierarchical and ultrametric barriers in the energy landscape of jammed granular matter
• Learning the Cosmic Web: Graph-based Classification of Simulated Galaxies by their Dark Matter Environments
• Distributed and Autonomic Minimum Spanning Trees
• Tree-cotree gauging for two-dimensional hierarchical splines
• SceneProp: Combining Neural Network and Markov Random Field for Scene-Graph Grounding
• Hyperbolic Continuous Structural Entropy for Hierarchical Clustering
• TDSR: Transparent Distributed Segment-Based Routing
• Irreducible network backbones: unbiased graph filtering via maximum entropy
• Spanning Tree Basis for Unbiased Averaging of Network Topologies
• Quantifying Generalization in Reinforcement Learning
• Drift Estimation with Graphical Models
• Linking the minimum spanning tree and edge betweenness to understand arterial corridors in an ecological network
• Leveraging Recursive Gumbel-Max Trick for Approximate Inference in Combinatorial Spaces
• Learning Max-Margin Tree Predictors
• Using Lagrangian dual information to generate degree constrained spanning trees
• Graphical Model-based Inference on Persistent Homology
• Graph Processing on FPGAs: Taxonomy, Survey, Challenges
• Whole-Genome Sequencing of Bacterial Pathogens: the Future of Nosocomial Outbreak Analysis
• Optimally cutting a surface into a disk
• Branch-and-cut-and-price algorithms for the Degree Constrained Minimum Spanning Tree Problem
• Upper and Lower Bounds for End-to-End Risks in Stochastic Robot Navigation
• Unbalanced Multi-Phase Distribution Grid Topology Estimation and Bus Phase Identification
• Spanning Tree Auxiliary Graphs
• Graph Regularized Autoencoder and its Application in Unsupervised Anomaly Detection
• Complex business ecosystem intelligence using AI-powered visual analytics
• Graph Hörmander Systems
• Study Morphology of Minimum Spanning Tree Problem and Generalized Algorithms
• Report on Optimal Substructure Techniques for Stellar, Gas and Combined Samples
• A graph theoretic approach for modelling wildlife corridors
• T-REGS: Minimum Spanning Tree Regularization for Self-Supervised Learning
• Expected Length of the Euclidean Minimum Spanning Tree and 1-norms of Chromatic Persistence Diagrams in the Plane
• Exploration through Generation: Applying GFlowNets to Structured Search
• Discriminative models for robust image classification
• Topological Alignment of Shared Vision-Language Embedding Space
• Selecting optimal minimum spanning trees that share a topological correspondence with phylogenetic trees
• Fast Self-Stabilizing Minimum Spanning Tree Construction Using Compact Nearest Common Ancestor Labeling Scheme
• Untangling Vascular Trees for Surgery and Interventional Radiology
• Sparse Graph Reconstruction and Seriation for Large-Scale Image Stacks
• Efficient Parameter-free Clustering Using First Neighbor Relations
• Incorporating Road Networks into Territory Design
• Using satellite imagery to measure the impacts of new highways: An application to India
• A Comprehensive Review of Real-Time Multi-View Multi-Person Markerless Motion Capture
• Efficient Structure from Motion for Oblique UAV Images Based on Maximal Spanning Tree Expansions
• Learning to Search via Retrospective Imitation
• Ultrametric Component Analysis with Application to Analysis of Text and\n of Emotion
• Filtering amplitude dependence of correlation dynamics in complex systems: application to the cryptocurrency market
• The Maximum Distance Problem and Minimal Spanning Trees
• Forest Density Estimation
• Minimum spanning acycle and lifetime of persistent homology in the Linial-Meshulam process
• Deep Open Snake Tracker for Vessel Tracing
• A Cycle Walk for Sampling Measures on Spanning Forests for Redistricting
• Community-level Contagion among Diverse Financial Assets
• Performative Thinking? The Brittle Correlation Between CoT Length and Problem Complexity
• Structural Tree Extraction from 3D Surfaces
• Convex minorant trees associated with Brownian paths and the continuum limit of the minimum spanning tree
• Attribute Filtering in Approximate Nearest Neighbor Search: An In-depth Experimental Study
• A Partition-Based Relaxation For Steiner Trees
• An Approximation Approach for Solving the Subpath Planning Problem
• On minimum spanning tree-like metric spaces
• Optimal Approximation Algorithms for Multi-agent Combinatorial Problems with Discounted Price Functions
• Combinatorial Network Optimization with Unknown Variables: Multi-Armed Bandits with Linear Rewards
• COREclust: a new package for a robust and scalable analysis of complex data
• A Structural Analysis of Population Graphs
• A Quantum Walk-Driven Algorithm for the Minimum Spanning Tree Problem under a Maximal Degree Constraint
• The Network Topology of the rs-EEG Associated with Cyberbullying Perpetration: The Role of Materialism as a Mediator and Parental Acceptance as a Moderator
• Assessing Graph Theory Students’ Use and Formulation of Definitions through the Van Hiele Model
• Bayesian learning of forest and tree graphical models
• Probing Syntax in Large Language Models: Successes and Remaining Challenges
• Extraordinarily high incidence rates of tuberculosis among Greenlanders living in Denmark, 2006–2022

Related

• The General Traveling Salesman Problem, Version 5
• Distance-regular graphs, the subconstituent algebra, and the Q-polynomial property
• Short survey about combinatorics on words and algorithmic methods in a ring (draft)
• A weighted graph problem from commutative algebra
• The Traveling Salesman Theorem for Jordan Curves in Hilbert Space