ON THE MINIMUM DIAMETER SPANNING TREE PROBLEM

被引：68
|
作者：
HASSIN, R
TAMIR, A
机构：
[1] Department of Statistics and Operations Research, School of Mathematical Sciences, Tel-Aviv University, Tel-Aviv
来源：
INFORMATION PROCESSING LETTERS | 1995年 / 53卷 / 02期
关键词：
ALGORITHMS; COMBINATORIAL PROBLEMS; MINIMUM DIAMETER SPANNING TREE; ABSOLUTE; 1-CENTER;
D O I：
10.1016/0020-0190(94)00183-Y
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
We point out a relation between the minimum diameter spanning tree of a graph and its absolute 1-center. We use this relation to solve the diameter problem and an extension of its efficiently.
引用
收藏
页码：109 / 111
页数：3
相关论文
共 50 条
  • [41] An algorithm for inverse minimum spanning tree problem
    Zhang, JH
    Xu, SJ
    Ma, ZF
    OPTIMIZATION METHODS & SOFTWARE, 1997, 8 (01): : 69 - 84
  • [42] THE MINIMUM SPANNING TREE PROBLEM ON A PLANAR GRAPH
    MATSUI, T
    DISCRETE APPLIED MATHEMATICS, 1995, 58 (01) : 91 - 94
  • [43] A Minimum Spanning Tree Problem in Uncertain Networks
    He, FangGuo
    Shao, GuiMing
    ADVANCES IN MULTIMEDIA, SOFTWARE ENGINEERING AND COMPUTING, VOL 1, 2011, 128 : 677 - 683
  • [44] RAMP for the capacitated minimum spanning tree problem
    Rego, Cesar
    Mathew, Frank
    Glover, Fred
    ANNALS OF OPERATIONS RESEARCH, 2010, 181 (01) : 661 - 681
  • [45] The minimum spanning tree problem with fuzzy costs
    Janiak, Adam
    Kasperski, Adam
    FUZZY OPTIMIZATION AND DECISION MAKING, 2008, 7 (02) : 105 - 118
  • [46] Fully Retroactive Minimum Spanning Tree Problem
    de Andrade Junior, Jose Wagner
    Seabra, Rodrigo Duarte
    COMPUTER JOURNAL, 2022, 65 (04): : 973 - 982
  • [47] Solving the Quadratic Minimum Spanning Tree Problem
    Cordone, Roberto
    Passeri, Gianluca
    APPLIED MATHEMATICS AND COMPUTATION, 2012, 218 (23) : 11597 - 11612
  • [48] The Minimum-Area Spanning Tree problem
    Carmi, Paz
    Katz, Matthew J.
    Mitchell, Joseph S. B.
    COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2006, 35 (03): : 218 - 225
  • [49] The Budgeted Labeled Minimum Spanning Tree Problem
    Cerulli, Raffaele
    D'Ambrosio, Ciriaco
    Serra, Domenico
    Sorgente, Carmine
    MATHEMATICS, 2024, 12 (02)
  • [50] Minimum Spanning Tree Problem with Label Selection
    Fujiyoshi, Akio
    Suzuki, Masakazu
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2011, E94D (02) : 233 - 239
12345