A Distributed Algorithm for Minimum-Weight Spanning Trees | ACM Transactions on Programming Languages and Systems
- ️SpiraP. M.
- ️Sat Jan 01 1983
New Citation Alert added!
This alert has been successfully added and will be sent to:
You will be notified whenever a record that you have chosen has been cited.
New Citation Alert!
References
[1]
DALAL, Y. Broadcast protocols in packet switched computer networks. Tech. Rep. 128, Dep. of Electrical Engineering, Stanford Univ., Apr. 1977 (revised version for publication in preparation).
[2]
DIJKSTRA, E. Two problems in connection with graphs. Numer. Math. I (1959), 269-271.
[3]
HUMBLET, P.A. A distributed algorithm for minimum weight directed spanning trees. Rep. LIDS-P-1149, Laboratory for Information and Decision Systems, Massachusetts Inst. of Technology, Cambridge, Mass., Sept. 1981.
[4]
KRUSKAL, J.B. On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. Am. Math. Soc. 7 (1956), 48-50.
[5]
LAWLER, E. Combinatorial Optimization-Networks and Matroids. Holt, Rinehart & Winston, New York, 1976.
[6]
LIU, C.L. Introduction to Combinatorial Mathematics. McGraw Hill, New York, 1968.
[7]
PRIM, R.C. Shortest connection networks and some generalizations. Bell Syst. Tech. J. 36 (1957), 1389-1401.
[8]
SPmA, P. Communication complexity of distributed minimum spanning tree algorithms. In Proceedings, 2nd Berkeley Conference on Distributed Data Management and Computer Networks, Berkeley, Calif., June 1977.
[9]
YAO, A.C.C. An O(E log log V) algorithm for finding minimum spanning trees. Inf. Process. Lett. 4 (1975), 21-23.
- Jiang JZhou DHe MYue XZhang S(2025)GSA‐Net: Global Spatial Structure‐Aware Attention Network for Liver Segmentation in MR Images With Respiratory ArtifactsIET Image Processing10.1049/ipr2.7001019:1Online publication date: 12-Feb-2025
- Saki HZangeneh AAghaei J(2025)Distributed minimum spanning tree approach for critical load restoration using microgrid formation in resilient distribution systemsElectric Power Systems Research10.1016/j.epsr.2024.111186239(111186)Online publication date: Feb-2025
- Heydt OKublenz SOssona de Mendez PSiebertz SVigny A(2025)Distributed domination on sparse graph classesEuropean Journal of Combinatorics10.1016/j.ejc.2023.103773123(103773)Online publication date: Jan-2025
- Show More Cited By
Index Terms
A Distributed Algorithm for Minimum-Weight Spanning Trees
Recommendations
Low-Degree Spanning Trees of Small Weight
Given $n$ points in the plane, the degree-$K$ spanning-tree problem asks for a spanning tree of minimum weight in which the degree of each vertex is at most $K$. This paper addresses the problem of computing low-weight degree-$K$ spanning trees for $K>2$...
Degree-bounded minimum spanning trees
Given n points in the Euclidean plane, the degree-@d minimum spanning tree (MST) problem asks for a spanning tree of minimum weight in which the degree of each vertex is at most @d. The problem is NP-hard for 2@__ __@d@__ __3, while the NP-hardness of ...
Comments
Information & Contributors
Information
Published In
ACM Transactions on Programming Languages and Systems Volume 5, Issue 1
Jan. 1983
125 pages
Copyright © 1983 ACM.
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 01 January 1983
Published in TOPLAS Volume 5, Issue 1
Permissions
Request permissions for this article.
Check for updates
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- Downloads (Last 12 months)757
- Downloads (Last 6 weeks)59
Reflects downloads up to 02 Mar 2025
Other Metrics
Citations
- Jiang JZhou DHe MYue XZhang S(2025)GSA‐Net: Global Spatial Structure‐Aware Attention Network for Liver Segmentation in MR Images With Respiratory ArtifactsIET Image Processing10.1049/ipr2.7001019:1Online publication date: 12-Feb-2025
- Saki HZangeneh AAghaei J(2025)Distributed minimum spanning tree approach for critical load restoration using microgrid formation in resilient distribution systemsElectric Power Systems Research10.1016/j.epsr.2024.111186239(111186)Online publication date: Feb-2025
- Heydt OKublenz SOssona de Mendez PSiebertz SVigny A(2025)Distributed domination on sparse graph classesEuropean Journal of Combinatorics10.1016/j.ejc.2023.103773123(103773)Online publication date: Jan-2025
- Kshemkalyani AKumar MMolla ASharma G(2025)Faster Leader Election and Its Applications for Mobile Agents with Parameter AdviceDistributed Computing and Intelligent Technology10.1007/978-3-031-81404-4_9(108-123)Online publication date: 8-Jan-2025
- Jung WPark CLee SKim H(2024)Enhancing UAV Swarm Tactics with Edge AI: Adaptive Decision Making in Changing EnvironmentsDrones10.3390/drones81005828:10(582)Online publication date: 15-Oct-2024
- Meng LShao YYuan LLai LCheng PLi XYu WZhang WLin XZhou J(2024)A Survey of Distributed Graph Algorithms on Massive GraphsACM Computing Surveys10.1145/369496657:2(1-39)Online publication date: 10-Oct-2024
- Ghaffari MWang BMohar BShinkar IO'Donnell R(2024)Lenzen’s Distributed Routing Generalized: A Full Characterization of Constant-Time RoutabilityProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649627(1877-1888)Online publication date: 10-Jun-2024
- Yang ZGhubaish AJain RShapourian HShabani A(2024)Asynchronous entanglement routing for the quantum internetAVS Quantum Science10.1116/5.01728196:1Online publication date: 18-Jan-2024
- Tran QLiu Y(2024)Robust, Flexible and Safe Cooperative Navigation for Multirobot Systems Under Disturbances and Input Saturation2024 13th International Workshop on Robot Motion and Control (RoMoCo)10.1109/RoMoCo60539.2024.10604378(124-129)Online publication date: 2-Jul-2024
- Liang ZLyu XRen CLi NLi K(2024)Communication-Efficient Topology Orchestration for Distributed Learning in UAV Networks2024 International Wireless Communications and Mobile Computing (IWCMC)10.1109/IWCMC61514.2024.10592528(662-667)Online publication date: 27-May-2024
- Show More Cited By
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.