MINIMUM-COST SPANNING TREE AS A PATH-FINDING PROBLEM

被引：23
|
作者：
MAGGS, BM [1 ]
PLOTKIN, SA [1 ]
机构：
[1] AT&T BELL LABS,MURRAY HILL,NJ 07974
来源：
INFORMATION PROCESSING LETTERS | 1988年 / 26卷 / 06期
基金：
美国国家科学基金会;
关键词：
COMPUTER PROGRAMMING - Algorithms - COMPUTER SYSTEMS; DIGITAL - Parallel Processing;
D O I：
10.1016/0020-0190(88)90185-8
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
We show that the minimum-cost spanning tree is a special case of the closed semiring path-finding problem. This observation gives us a nonrecursive algorithm for finding minimum-cost spanning trees on mesh-connected computers which has the same asymptotic running time as but is much simpler than the previous recursive algorithms.
引用
收藏
页码：291 / 293
页数：3
相关论文
共 50 条
  • [1] Submodularity of minimum-cost spanning tree games
    Kobayashi, Masayuki
    Okamoto, Yoshio
    NETWORKS, 2014, 63 (03) : 231 - 238
  • [2] APPROXIMATING MINIMUM-COST GRAPH PROBLEMS WITH SPANNING TREE EDGES
    GOEMANS, MX
    WILLIAMSON, DP
    OPERATIONS RESEARCH LETTERS, 1994, 16 (04) : 183 - 189
  • [3] Finding the minimum-cost path without cutting corners
    van Heekeren, R. Joop
    Faas, Frank G. A.
    van Vliet, Lucas J.
    IMAGE ANALYSIS, PROCEEDINGS, 2007, 4522 : 263 - +
  • [4] On approximability of the minimum-cost k-connected spanning subgraph problem
    Czumaj, A
    Lingas, A
    PROCEEDINGS OF THE TENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 1999, : 281 - 290
  • [5] Geometric Minimum Diameter Minimum Cost Spanning Tree Problem
    Seo, Dae Young
    Lee, D. T.
    Lin, Tien-Ching
    ALGORITHMS AND COMPUTATION, PROCEEDINGS, 2009, 5878 : 283 - +
  • [6] A NOTE ON FINDING MINIMUM-COST EDGE-DISJOINT SPANNING-TREES
    ROSKIND, J
    TARJAN, RE
    MATHEMATICS OF OPERATIONS RESEARCH, 1985, 10 (04) : 701 - 708
  • [7] Finding minimum-cost paths with minimum sharability
    Zheng, S. Q.
    Yang, Bing
    Yang, Mei
    Wang, Jianping
    INFOCOM 2007, VOLS 1-5, 2007, : 1532 - +
  • [8] A review of cooperative rules and their associated algorithms for minimum-cost spanning tree problems
    Gustavo Bergantiños
    Juan Vidal-Puga
    SERIEs, 2021, 12 : 73 - 100
  • [9] A review of cooperative rules and their associated algorithms for minimum-cost spanning tree problems
    Bergantinos, Gustavo
    Vidal-Puga, Juan
    SERIES-JOURNAL OF THE SPANISH ECONOMIC ASSOCIATION, 2021, 12 (01): : 73 - 100
  • [10] A claims problem approach to the cost allocation of a minimum cost spanning tree
    José-Manuel Giménez-Gómez
    Josep E. Peris
    Begoña Subiza
    Operational Research, 2022, 22 : 2785 - 2801
12345