A linear-time optimal-message distributed algorithm for minimum spanning trees

被引：0
|
作者：
Michalis Faloutsos
Mart Molle
机构：
[1] University of California Riverside,Department of Computer Science
来源：
Distributed Computing | 2004年 / 17卷
关键词：
Time Complexity; Span Tree; Optimal Time; Early Paper; Minimum Span Tree;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
In an earlier paper, Awerbuch presented an innovative distributed algorithm for solving minimum spanning tree (MST) problems that achieved optimal time and message complexity through the introduction of several advanced features. In this paper, we show that there are some cases where his algorithm can create cycles or fail to achieve optimal time complexity. We then show how to modify the algorithm to avoid these problems, and demonstrate both the correctness and optimality of the revised algorithm.
引用
收藏
页码：151 / 170
页数：19
相关论文
共 50 条
  • [1] A linear-time optimal-message distributed algorithm for minimum spanning trees
    Faloutsos, M
    Molle, M
    DISTRIBUTED COMPUTING, 2004, 17 (02) : 151 - 170
  • [2] A Time- and Message-Optimal Distributed Algorithm for Minimum Spanning Trees
    Pandurangan, Gopal
    Robinson, Peter
    Scquizzato, Michele
    STOC'17: PROCEEDINGS OF THE 49TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING, 2017, : 743 - 756
  • [3] A Time- and Message-Optimal Distributed Algorithm for Minimum Spanning Trees
    Pandurangan, Gopal
    Robinson, Peter
    Scquizzato, Michele
    ACM TRANSACTIONS ON ALGORITHMS, 2020, 16 (01)
  • [4] Randomized linear-time algorithm to find minimum spanning trees
    Stanford Univ, Stanford, United States
    J Assoc Comput Mach, 2 (321-328):
  • [5] An Even Simpler Linear-Time Algorithm for Verifying Minimum Spanning Trees
    Hagerup, Torben
    GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, 2010, 5911 : 178 - 189
  • [6] A RANDOMIZED LINEAR-TIME ALGORITHM TO FIND MINIMUM SPANNING-TREES
    KARGER, DR
    KLEIN, PN
    TARJAN, RE
    JOURNAL OF THE ASSOCIATION FOR COMPUTING MACHINERY, 1995, 42 (02): : 321 - 328
  • [7] A LINEAR-TIME ALGORITHM FOR FINDING A MINIMUM SPANNING PSEUDOFOREST
    GABOW, HN
    TARJAN, RE
    INFORMATION PROCESSING LETTERS, 1988, 27 (05) : 259 - 263
  • [8] Optimal layout of hexagonal minimum spanning trees in linear time
    Lin, GH
    Xue, GL
    ISCAS 2000: IEEE INTERNATIONAL SYMPOSIUM ON CIRCUITS AND SYSTEMS - PROCEEDINGS, VOL IV: EMERGING TECHNOLOGIES FOR THE 21ST CENTURY, 2000, : 633 - 636
  • [9] A linear-time algorithm to find independent spanning trees in maximal planar graphs
    Nagai, S
    Nakano, S
    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, 2001, E84A (05): : 1102 - 1109
  • [10] A linear-time algorithm to find independent spanning trees in maximal planar graphs
    Nagai, S.
    Nakano, S.-I.
    IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2001, E84-A (05) : 1102 - 1109
12345