Shortest Connection Networks And Some Generalizations

1957/11/01 by R. C. Prim · 40 citations
Computer Science · Engineering · Mathematics · #Graph theory and applications #Interconnection Networks and Systems #graph theory and CDMA systems

paper · doi:10.1002/j.1538-7305.1957.tb01515.x

crossref issued 1957/11/01 · crossref published 1957/11/01 · crossref published-print 1957/11/01 · openalex publication_date 1957/11/01 · crossref published-online 2013/07/29 · crossref created 2013/07/29 · crossref deposited 2020/10/14 · openalex created_date 2025/10/10 · crossref indexed 2026/07/31 · openalex updated_date 2026/08/01

Abstract

The basic problem considered is that of interconnecting a given set of terminals with a shortest possible network of direct links. Simple and practical procedures are given for solving this problem both graphically and computationally. It develops that these procedures also provide solutions for a much broader class of problems, containing other examples of practical interest.

Citations

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

Cited by

• Local limit of Prim's algorithm
• da4ml: Distributed Arithmetic for Real-time Neural Networks on FPGAs
• Lightweight Temporal Transformer Decomposition for Federated Autonomous Driving
• Derivational Probing: Unveiling the Layer-wise Derivation of Syntactic Structures in Neural Language Models
• LIGHT: Multi-Modal Text Linking on Historical Maps
• Cooperative Bistatic ISAC Systems for Low-Altitude Economy
• Graph-based Gossiping for Communication Efficiency in Decentralized Federated Learning
• An allocation rule for connection scheduling problems
• Graph-based regularization for regression problems with alignment and highly-correlated designs
• Fast-Converging Distributed Signal Estimation in Topology-Unconstrained Wireless Acoustic Sensor Networks
• New Dynamic Programming algorithm for the Multiobjective Minimum Spanning Tree problem
• Hamiltonian Graphs and the Traveling Salesman Problem
• GrAviPaSt's Lens to the Past: Unveiling the Evolution of Filamentary Structures
• A Formal Analysis of Algorithms for Matroids and Greedoids
• The diameter of the minimum spanning tree of the complete graph with inhomogeneous random weights
• A closed-form approach to Bayesian inference in tree-structured graphical models
• Median-joining networks for inferring intraspecific phylogenies
• Study on Resource Efficiency of Distributed Graph Processing
• Optimizing Age-of-Information in Piggyback Networks with Recurrent Data Generation
• Detecting regime switches in the dependence structure of high dimensional financial data
• Learning from Others in the Financial Market
• Learning Repetition-Invariant Representations for Polymer Informatics
• Visualizing the pulsar population using graph theory
• On the Minimum Spanning Tree for Directed Graphs with Potential Weights
• Minimum-weight spanning tree algorithms A survey and empirical study
• BreakLoops: A New Feature for the Multi-Gene, Multi-Cancer Family History-Based Model, Fam3Pro
• Information Filtering Networks: Theoretical Foundations, Generative Methodologies, and Real-World Applications
• Sporothrix davidellisii : A new pathogenic species belonging to the Sporothrix pallida complex
• A Minimal Spanning Tree algorithm for source detection in γ-ray images
• The spatial distribution of substellar objects in IC 348 and the Orion Trapezium cluster
• A study of Chinese regional hierarchical structure based on surnames
• The structures of embedded clusters in the Perseus, Serpens and Ophiuchus molecular clouds
• The (black) art of runtime evaluation: Are we comparing algorithms or implementations?
• A Distributed Algorithm for Minimum-Weight Spanning Trees
• Fibonacci heaps and their uses in improved network optimization algorithms
• Equivalence between priority queues and sorting
• The Nature of Computation
• Maximum Likelihood Reinforcement Learning
• Dijkstra's algorithm [wikipedia]
• Prim's algorithm [wikipedia]