Approximating the Degree-Bounded Minimum Diameter Spanning Tree Problem

被引：0
作者：
Jochen Könemann
Asaf Levin
Amitabh Sinha
机构：
[1] Department of Combinatorics and Optimization,
[2] University of Waterloo,undefined
[3] 200 University Avenue West,undefined
[4] Waterloo,undefined
[5] Ontario,undefined
[6] N2L 3G1,undefined
[7] Faculty of Industrial Engineering and Management,undefined
[8] The Technion,undefined
[9] Haifa 32000,undefined
[10] Business School,undefined
[11] University of Michigan,undefined
[12] Ann Arbor,undefined
[13] MI 48103,undefined
来源：
Algorithmica | 2005年 / 41卷
关键词：
Approximation algorithms; Spanning trees; Bicriteria approximation; Degree-bounded spanning trees;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
We consider the problem of finding a minimum diameter spanning tree with maximum node degree $B$ in a complete undirected edge-weighted graph. We provide an $O(\sqrt{\log_Bn})$-approximation algorithm for the problem. Our algorithm is purely combinatorial, and relies on a combination of filtering and divide and conquer.
引用
收藏
页码：117 / 129
页数：12
相关论文
共 50 条
  • [41] The minimum spanning tree problem with non-terminal set
    Zhang, Tongquan
    Yin, Ying
    INFORMATION PROCESSING LETTERS, 2012, 112 (17-18) : 688 - 690
  • [42] An approximation algorithm for the balanced capacitated minimum spanning tree problem
    Fallah H.
    Didehvar F.
    Rahmati F.
    Scientia Iranica, 2021, 28 (3 D) : 1479 - 1492
  • [43] Minimum spanning tree cycle intersection problem on outerplanar graphs
    Su, Tai -Yu
    DISCRETE APPLIED MATHEMATICS, 2024, 343 : 328 - 339
  • [44] Better Hardness Results for the Minimum Spanning Tree Congestion Problem
    Luu, Huong
    Chrobak, Marek
    ALGORITHMICA, 2025, 87 (01) : 148 - 165
  • [45] An approximation algorithm for the balanced capacitated minimum spanning tree problem
    Fallah, H.
    Didehvar, F.
    Rahmati, F.
    SCIENTIA IRANICA, 2021, 28 (03) : 1479 - 1492
  • [46] Solving diameter-constrained minimum spanning tree problems by constraint programming
    Noronha, Thiago F.
    Ribeiro, Celso C.
    Santos, Andrea C.
    INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, 2010, 17 (05) : 653 - 665
  • [47] A biased random-key genetic algorithm for the capacitated minimum spanning tree problem
    Ruiz, Efrain
    Albareda-Sambola, Maria
    Fernandez, Elena
    Resende, Mauricio G. C.
    COMPUTERS & OPERATIONS RESEARCH, 2015, 57 : 95 - 108
  • [48] Approximation Algorithms for the Capacitated Minimum Spanning Tree Problem and its Variants in Network Design
    Jothi, Raja
    Raghavachari, Balaji
    ACM TRANSACTIONS ON ALGORITHMS, 2005, 1 (02) : 265 - 282
  • [49] General variable neighborhood search for the minimum stretch spanning tree problem
    Yogita Singh Kardam
    Kamal Srivastava
    Rafael Martí
    Optimization Letters, 2023, 17 : 2005 - 2031
  • [50] Minimum restricted diameter spanning trees
    Hassin, R
    Levin, A
    DISCRETE APPLIED MATHEMATICS, 2004, 137 (03) : 343 - 357
12345