article

A parallel algorithm for computing minimum spanning trees

Authors:

Donald B. Johnson,

Panagiotis MetaxasAuthors Info & Claims

Journal of Algorithms, Volume 19, Issue 3

Pages 383 - 401

https://doi.org/10.1006/jagm.1995.1043

Published: 01 November 1995 Publication History

Abstract

No abstract available.

Cited By

View all

Flocchini PEnriquez TPagli LPrencipe GSantoro N(2007)Distributed computation of all node replacements of a minimum spanning treeProceedings of the 13th international Euro-Par conference on Parallel Processing10.5555/2391541.2391612(598-607)Online publication date: 28-Aug-2007
https://dl.acm.org/doi/10.5555/2391541.2391612
Bang-Jensen JHuang JIbarra L(2007)Recognizing and representing proper interval graphs in parallel using merging and sortingDiscrete Applied Mathematics10.1016/j.dam.2006.07.005155:4(442-456)Online publication date: 20-Feb-2007
https://dl.acm.org/doi/10.1016/j.dam.2006.07.005
Nepomniaschaya A(2005)Associative parallel algorithm for dynamic reconstruction of a minimum spanning tree after deletion of a vertexProceedings of the 8th international conference on Parallel Computing Technologies10.1007/11535294_14(159-173)Online publication date: 5-Sep-2005
https://dl.acm.org/doi/10.1007/11535294_14
Show More Cited By

Index Terms

A parallel algorithm for computing minimum spanning trees

Recommendations

Computing minimum spanning trees efficiently
ACM '72: Proceedings of the ACM annual conference - Volume 1

A ubiquitous problem in mathematical programming is the calculation of minimum spanning trees. Minimum spanning tree algorithms find application in such diverse areas as: least cost electrical wiring, minimum cost connecting communication and ...
Balancing minimum spanning trees and multiple-source minimum routing cost spanning trees on metric graphs

Both the building cost and the multiple-source routing cost are important considerations in construction of a network system. A spanning tree with minimum building cost among all spanning trees is called a minimum spanning tree (MST), and a spanning ...
A parallel algorithm for k-minimum spanning trees
PAS '97: Proceedings of the 2nd AIZU International Symposium on Parallel Algorithms / Architecture Synthesis

A parallel algorithm to find k, 2/spl les/k/spl les/n/sup n-2/, spanning trees from a connected, weighted and undirected graph C(V, E, W) in the order of increasing weight is presented. It runs in O(T(n)+klogn) time with O(n/sup 2//log n) processors on ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of Algorithms Volume 19, Issue 3

Nov. 1995

171 pages

ISSN:0196-6774

Editors:
Zvi Galil
Columbia Univ., New York, NY and Tel Aviv Univ., Tel Aviv, Israel
,
David S. Johnson
At&T Bell Labs.,Murray Hills, NJ
,
Donald E. Knuth
Stanford Univ., Stanford, CA

Issue’s Table of Contents

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 November 1995

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Flocchini PEnriquez TPagli LPrencipe GSantoro N(2007)Distributed computation of all node replacements of a minimum spanning treeProceedings of the 13th international Euro-Par conference on Parallel Processing10.5555/2391541.2391612(598-607)Online publication date: 28-Aug-2007
https://dl.acm.org/doi/10.5555/2391541.2391612
Bang-Jensen JHuang JIbarra L(2007)Recognizing and representing proper interval graphs in parallel using merging and sortingDiscrete Applied Mathematics10.1016/j.dam.2006.07.005155:4(442-456)Online publication date: 20-Feb-2007
https://dl.acm.org/doi/10.1016/j.dam.2006.07.005
Nepomniaschaya A(2005)Associative parallel algorithm for dynamic reconstruction of a minimum spanning tree after deletion of a vertexProceedings of the 8th international conference on Parallel Computing Technologies10.1007/11535294_14(159-173)Online publication date: 5-Sep-2005
https://dl.acm.org/doi/10.1007/11535294_14
Chong KHan YIgarashi YLam T(2003)Improving the efficiency of parallel minimum spanning tree algorithmsDiscrete Applied Mathematics10.1016/S0166-218X(02)00560-7126:1(33-54)Online publication date: 1-Mar-2003
https://dl.acm.org/doi/10.1016/S0166-218X%2802%2900560-7
Halperin SZwick U(2001)Optimal Randomized EREW PRAM Algorithms for Finding Spanning ForestsJournal of Algorithms10.1006/jagm.2000.114639:1(1-46)Online publication date: 1-Apr-2001
https://dl.acm.org/doi/10.1006/jagm.2000.1146
Chong KHan YIgarashi YLam T(1999)Improving parallel computation with fast integer sortingProceedings of the 5th annual international conference on Computing and combinatorics10.5555/1765751.1765815(452-461)Online publication date: 26-Jul-1999
https://dl.acm.org/doi/10.5555/1765751.1765815
Adler MDittrich WJuurlink BKutyłowski MRieping IMiller GGibbons P(1998)Communication-optimal parallel minimum spanning tree algorithms (extended abstract)Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures10.1145/277651.277662(27-36)Online publication date: 1-Jun-1998
https://dl.acm.org/doi/10.1145/277651.277662
Kessler CTräff JBlelloch G(1996)A library of basic PRAM algorithms and its implementation in FORKProceedings of the eighth annual ACM symposium on Parallel Algorithms and Architectures10.1145/237502.237545(193-195)Online publication date: 24-Jun-1996
https://dl.acm.org/doi/10.1145/237502.237545

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

Cited By

Index Terms

Recommendations

Computing minimum spanning trees efficiently

Balancing minimum spanning trees and multiple-source minimum routing cost spanning trees on metric graphs

A parallel algorithm for k-minimum spanning trees

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations