On the shortest spanning subtree of a graph and the traveling salesman problem
1956/02/01 by Joseph B. Kruskal · 3,891 citations
Chemistry · Computer Science · Mathematics · #Advanced Graph Theory Research #Algebraic number #Chemistry #Combinatorics #Discrete mathematics #Graph #Graph theory and applications #Mathematical analysis #Mathematical optimization #Mathematics #Ring (chemistry) #Travelling salesman problem
paper · pdf · doi:10.1090/s0002-9939-1956-0078686-7
published in Proceedings of the American Mathematical Society 7(1), 48-50 (American Mathematical Society (AMS))
crossref issued 1956/02/01 · crossref published 1956/02/01 · crossref published-print 1956/02/01 · openalex publication_date 1956/02/01 · crossref created 2010/06/30 · openalex created_date 2025/10/10 · crossref deposited 2026/04/05 · openalex updated_date 2026/08/06 · crossref indexed 2026/08/07
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. 46266. 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
- An end-to-end assembly of the Aedes aegypti genome
- 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 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
- Chinese roads in India: The effect of transport infrastructure on economic development
- 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
- Probabilistic Structure Learning for EEG/MEG Source Imaging with Hierarchical Graph Prior
- Automatic kidney segmentation in ultrasound images using subsequent boundary distance regression and pixelwise classification networks
- Clustering to Maximize the Ratio of Split to Diameter
- Triconed Graphs, weighted forests, and h-vectors of matroid complexes
- New genetic algorithm approach for the min-degree constrained minimum spanning tree
- A Lagrangean approach to the degree-constrained minimum spanning tree problem
- Scene Parsing with Multiscale Feature Learning, Purity Trees, and Optimal Covers
- Group Invariance and Computational Sufficiency
- Learning directed acyclic graphs via bootstrap aggregating
- Anonimos: An LP based Approach for Anonymizing Weighted Social Network Graphs
- Spectral analysis and clustering of large stochastic networks. Application to the Lennard-Jones-75 cluster
- Steiner's problem in graphs and its implications
- A branch and cut method for the degree-constrained minimum spanning tree problem
- Lower and upper bounds for the degree‐constrained minimum spanning tree problem
- New Dynamic Programming algorithm for the Multiobjective Minimum Spanning Tree problem
- An allocation rule for connection scheduling problems
- Distributed Resource Management in Systems of Systems: An Architecture Perspective
- Attention Routing: track-assignment detailed routing using attention-based reinforcement learning
- Some Network Optimization Models under Diverse Uncertain Environments
- Adaptive Inferential Method for Monotone Graph Invariants
- An adaptive minimum spanning tree multi-element method for uncertainty\n quantification of smooth and discontinuous responses
- On the Structure of the Graph of Unique Symmetric Base Exchanges of Bispanning Graphs
- Time Complexity Analysis of Evolutionary Algorithms for 2-Hop (1,2)-Minimum Spanning Tree Problem
- Linear Time Algorithms Based on Multilevel Prefix Tree for Finding Shortest Path with Positive Weights and Minimum Spanning Tree in a Networks
- Utility-Based Graph Summarization: New and Improved
- Gapped Parent Hamiltonians for the Strongly Deformed Toric Code
- Local limit of Prim's algorithm
- On Pseudocodewords and Improved Union Bound of Linear Programming Decoding of HDPC Codes
- Decentralized Learning of Tree-Structured Gaussian Graphical Models from Noisy Data
- Efficient and Accurate Image Provenance Analysis: A Scalable Pipeline for Large-scale Images
- A Family of Blockwise One-Factor Distributions for Modelling High-Dimensional Binary Data
- On the Neuwirth conjecture for knots
- A General System for Heuristic Solution of Convex Problems over Nonconvex Sets
- Improved Topology-Independent Distributed Adaptive Node-Specific Signal Estimation for Wireless Acoustic Sensor Networks
- Cooperative Bistatic ISAC Systems for Low-Altitude Economy
- Toward Understanding Similarity of Visualization Techniques
- Vine Copulas as Differentiable Computational Graphs
- Graph-based Gossiping for Communication Efficiency in Decentralized Federated Learning
- Approximation Algorithms for Budget Constrained Network Upgradeable Problems
- Tree density estimation
- Lower Bounds for the Probability of a Union via Chordal Graphs
- Optimization of Graph Total Variation via Active-Set-based Combinatorial Reconditioning
- Group Key Agreement Protocol for MANETs Based on HSK Scheme
- Capacities of repeater-assisted quantum communications
- Network Backboning with Noisy Data
- SQLens: An End-to-End Framework for Error Detection and Correction in Text-to-SQL
- A Construction of Bayesian Networks from Databases Based on an MDL Principle
- Shortest Connection Networks And Some Generalizations
- Fast-Converging Distributed Signal Estimation in Topology-Unconstrained Wireless Acoustic Sensor Networks
- Hamiltonian Graphs and the Traveling Salesman Problem
- Does electrification cause industrial development? Grid expansion and firm turnover in Indonesia
- Primal-Dual Neural Algorithmic Reasoning
- A Formal Analysis of Algorithms for Matroids and Greedoids
- Bayesian Mixture Models for Frequent Itemset Discovery
- The diameter of the minimum spanning tree of the complete graph with inhomogeneous random weights
- Gradient Estimation with Stochastic Softmax Tricks
- Semantic Networks as Clues: A Theoretical Foundation and Process Optimization for Semantic Network Construction
- Exact Solutions for the Carrier–Vehicle Traveling Salesman Problem
- Exploring Temporal Graphs with Frequent and Regular Edges
- Optimizing Age-of-Information in Piggyback Networks with Recurrent Data Generation
- Greedy Heuristic Guided by Lexicographic Excellence
- Extracting the main trend in a dataset: the Sequencer algorithm
- Linear-Time Pointer-Machine Algorithms for Path-Evaluation Problems on Trees and Graphs
- Visualizing the pulsar population using graph theory
- Kantorovich distance on a finite metric space
- Algorithms and Experiments Comparing Two Hierarchical Drawing Frameworks
- Matching a Desired Causal State via Shift Interventions
- Minimum-weight spanning tree algorithms A survey and empirical study
- A New Self-Stabilizing Minimum Spanning Tree Construction with Loop-free Property
- The complexity of acyclic conjunctive queries
- Foreign Exchange Market Performance: Evidence from Bivariate Time Series Approach
- BreakLoops: A New Feature for the Multi-Gene, Multi-Cancer Family History-Based Model, Fam3Pro
- Parameters of proteome evolution from histograms of amino-acid sequence identities of paralogous proteins
- Robust inference of trees
- A Minimal Spanning Tree algorithm for source detection in γ-ray images
- A study of Chinese regional hierarchical structure based on surnames
- Does greed help a forager survive?
- Topology of the correlation networks among major currencies using hierarchical structure methods
- The structures of embedded clusters in the Perseus, Serpens and Ophiuchus molecular clouds
- Machine learning meets complex networks via coalescent embedding in the hyperbolic space
- Classification of Coupled Dynamical Systems with Multiple Delays: Finding the Minimal Number of Delays
- A greedy-navigator approach to navigable city plans
- A Distributed Algorithm for Minimum-Weight Spanning Trees
- Genetic analysis reveals the wild ancestors of the llama and the alpaca
- Efficiency and robustness in ant networks ofgalleries
- A polynomial-time algorithm for determining the isomorphism of graphs of fixed genus
- The software space of science
- The Nature of Computation
- Topological Risk Parity
- Parallel graph algorithms
- Parallelization of Minimum Spanning Tree Algorithms Using Distributed Memory Architectures
- Formal Procedures for Connecting Terminals with a Minimum Total Wire Length
- An Approach to Parallelize Kruskal's Algorithm Using Helper Threads
- Finding Minimum Spanning Trees
- Priority queues with update and finding minimum spanning trees
- Voronoi diagrams—a survey of a fundamental geometric data structure
- Submodular Functions, Matroids, and Certain Polyhedra
- Investigating the Interplay of Parameterization and Optimizer in Gradient-Free Topology Optimization: A Cantilever Beam Case Study
- On Steiner Minimal Trees with Rectilinear Distance
- A faster approximation algorithm for the Steiner problem in graphs
- Minimum sum of diameters clustering
- Testing the randomness in the sky-distribution of gamma-ray bursts
- A General Approximation Technique for Constrained Forest Problems
- On the value of a random minimum spanning tree problem
- Otakar Borůvka on minimum spanning tree problem Translation of both the 1926 papers, comments, history
- Automatic analysis of artistic paintings using information-based measures
- Metastability, spectrum, and eigencurrents of the Lennard-Jones-38 network
- Network Topology Evaluation and Transitive Alignments for Molecular Networking
- Constructive Tensor Field Theory
- A Fractal Dimension for Measures via Persistent Homology
- New Algorithms for Incremental Minimum Spanning Trees and Temporal Graph Applications
- Stochastic spanning tree problem
- An ALNS algorithm for the static dial-a-ride problem with ride and waiting time minimization
- Balancing minimum spanning trees and shortest-path trees
- Digraphs of potential barriers: properties of their tree structure and algorithm for constructing minimum spanning forests
- Maximum Split Clustering Under Connectivity Constraints
- Linear estimating equations for exponential families with application to Gaussian linear concentration models
- Speedup Chip Yield Analysis by Improved Quantum Bayesian Inference
- Time evolution of the behaviour of Brazilian legislative Representatives using a complex network approach
- Renormalization of Feynman amplitudes on manifolds by spectral zeta regularization and blow-ups
- Detection of the first X-ray selected large AGN group
- Efficient ring perception for the Chemistry Development Kit
- An optimal network for passenger traffic
- A Note on Two Problems in Connexion with Graphs
- Closest-point problems
- Work-Efficient Batch-Incremental Minimum Spanning Trees with Applications to the Sliding-Window Model
- A Logic for Non-deterministic Parallel Abstract State Machines
- Parsimonious modeling with information filtering networks
- Large scale structure in the SDSS galaxy survey
- Approximate hierarchical density-based clustering using graph-based search indexes
- Approximating discrete probability distributions with dependence trees
- Simplified and Verified: A Second Look at a Proof-Producing Union-Find Algorithm
- Letter to the Editor—The Maximum Capacity Route Problem
- LayerFlow: Layer-wise Exploration of LLM Embeddings using Uncertainty-aware Interlinked Projections
- Spectral and Topological Abnormalities of Resting and Task State EEG in Chinese Children with Developmental Dyslexia
- Kruskal's algorithm [wikipedia]
- PHYLOViZ: phylogenetic inference and data visualization for sequence based typing methods. [europepmc]
- Efficient ring perception for the Chemistry Development Kit. [europepmc]
- Bayesian networks in neuroscience: a survey. [europepmc]
- Declining functional connectivity and changing hub locations in Alzheimer's disease: an EEG study. [europepmc]
- Resting-State Functional Connectivity and Network Analysis of Cerebellum with Respect to [corrected] IQ and Gender. [europepmc]
- Topological Filtering of Dynamic Functional Brain Networks Unfolds Informative Chronnectomics: A Novel Data-Driven Thresholding Scheme Based on Orthogonal Minimal Spanning Trees (OMSTs). [europepmc]
- MIST: Accurate and Scalable Microscopy Image Stitching Tool with Stage Modeling and Error Minimization. [europepmc]
- Visualizing the GPCR Network: Classification and Evolution. [europepmc]
- Machine learning meets complex networks via coalescent embedding in the hyperbolic space. [europepmc]
- Disrupted Brain Network in Children with Autism Spectrum Disorder. [europepmc]
- Classification of Alzheimer's Disease, Mild Cognitive Impairment, and Normal Controls With Subnetwork Selection and Graph Kernel Principal Component Analysis Based on Minimum Spanning Tree Brain Functional Network. [europepmc]
- Localization of the Epileptogenic Zone Using Interictal MEG and Machine Learning in a Large Cohort of Drug-Resistant Epilepsy Patients. [europepmc]
- A Comprehensive Review of Magnetoencephalography (MEG) Studies for Brain Functionality in Healthy Aging and Alzheimer's Disease (AD). [europepmc]
- Amnestic Mild Cognitive Impairment Is Associated With Frequency-Specific Brain Network Alterations in Temporal Poles. [europepmc]
- Mindfulness Meditation Is Related to Long-Lasting Changes in Hippocampal Functional Topology during Resting State: A Magnetoencephalography Study. [europepmc]
- Motor Skills as Moderators of Core Symptoms in Autism Spectrum Disorders: Preliminary Data From an Exploratory Analysis With Artificial Neural Networks. [europepmc]
- Mutations in the SPAST gene causing hereditary spastic paraplegia are related to global topological alterations in brain functional networks. [europepmc]
- Risk Assessment After a Severe Hospital-Acquired Infection Associated With Carbapenemase-Producing Pseudomonas aeruginosa. [europepmc]
- Visualization of very large high-dimensional data sets as minimum spanning trees. [europepmc]
- Functional brain network topology across the menstrual cycle is estradiol dependent and correlates with individual well-being. [europepmc]
- Stress management using fNIRS and binaural beats stimulation. [europepmc]
- Jasmine and Iris: population-scale structural variant comparison and analysis. [europepmc]
- Effectiveness of molecular fingerprints for exploring the chemical space of natural products. [europepmc]
- Advances in Medical Image Segmentation: A Comprehensive Review of Traditional, Deep Learning and Hybrid Approaches. [europepmc]
- Coverage bias in small molecule machine learning. [europepmc]
Related