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 条
  • [31] The Minimum Moving Spanning Tree Problem
    Akitaya H.A.
    Biniaz A.
    Bose P.
    De Carufel J.-L.
    Maheshwari A.
    da Silveira L.F.S.X.
    Smid M.
    Journal of Graph Algorithms and Applications, 2023, 27 (01) : 1 - 18
  • [32] The minimum spanning tree problem in archaeology
    Hage, P
    Harary, F
    James, B
    AMERICAN ANTIQUITY, 1996, 61 (01) : 149 - 155
  • [33] The Minimum Moving Spanning Tree Problem
    Akitaya, Hugo A.
    Biniaz, Ahmad
    Bose, Prosenjit
    De Carufel, Jean-Lou
    Maheshwari, Anil
    da Silveira, Luis Fernando Schultz Xavier
    Smid, Michiel
    ALGORITHMS AND DATA STRUCTURES, WADS 2021, 2021, 12808 : 15 - 28
  • [34] A Lagrangian Relax-and-Cut Approach for the Bounded Diameter Minimum Spanning Tree Problem
    Raidl, Guenther R.
    Gruber, Martin
    NUMERICAL ANALYSIS AND APPLIED MATHEMATICS, 2008, 1048 : 446 - 449
  • [35] A New Hybrid Genetic Algorithm for Solving the Bounded Diameter Minimum Spanning Tree Problem
    Huynh Thi Thanh Binh
    Nguyen Xuan, Hoai
    McKay, R. I.
    2008 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION, VOLS 1-8, 2008, : 3128 - +
  • [36] Fast Heuristics for Large Instances of the Euclidean Bounded Diameter Minimum Spanning Tree Problem
    Patvardhan, C.
    Prakash, V. Prem
    Srivastav, A.
    INFORMATICA-JOURNAL OF COMPUTING AND INFORMATICS, 2015, 39 (03): : 281 - 292
  • [37] A learning automata based approach to the bounded-diameter minimum spanning tree problem
    Torkestani, Javad Akbari
    Rezaei, Zahra
    JOURNAL OF THE CHINESE INSTITUTE OF ENGINEERS, 2013, 36 (06) : 749 - 759
  • [38] A distributed algorithm for constructing a minimum diameter spanning tree
    Bui, M
    Butelle, F
    Lavault, C
    JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 2004, 64 (05) : 571 - 577
  • [39] Reload cost problems: minimum diameter spanning tree
    Wirth, HC
    Steffan, J
    DISCRETE APPLIED MATHEMATICS, 2001, 113 (01) : 73 - 85
  • [40] The multilevel capacitated minimum spanning tree problem
    Gamvros, Ioannis
    Golden, Bruce
    Raghavan, S.
    INFORMS JOURNAL ON COMPUTING, 2006, 18 (03) : 348 - 365
12345