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 条

[11] Approximating the minimum spanning tree weight in sublinear time
Chazelle, B
Rubinfeld, R
Trevisan, L
SIAM JOURNAL ON COMPUTING, 2005, 34 (06) : 1370 - 1379
[12] Approximating average bounded-angle minimum spanning trees
Biniaz, Ahmad
Bose, Prosenjit
Devaney, Patrick
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2025, 128
[13] Local search for the minimum label spanning tree problem with bounded color classes
Brüggemann, T
Monnot, J
Woeginger, GJ
OPERATIONS RESEARCH LETTERS, 2003, 31 (03) : 195 - 201
[14] On the minimum label spanning tree problem
Krumke, SO
Wirth, HC
INFORMATION PROCESSING LETTERS, 1998, 66 (02) : 81 - 85
[15] 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
[16] When Diameter Matters: Parameterized Approximation Algorithms for Bounded Diameter Minimum Steiner Tree Problem
Ali Mashreghi
Alireza Zarei
Theory of Computing Systems, 2016, 58 : 287 - 303
[17] When Diameter Matters: Parameterized Approximation Algorithms for Bounded Diameter Minimum Steiner Tree Problem
Mashreghi, Ali
Zarei, Alireza
THEORY OF COMPUTING SYSTEMS, 2016, 58 (02) : 287 - 303
[18] 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
[19] Approximating bounded-degree spanning trees and connected factors with leaves
Kern, Walter
Manthey, Bodo
OPERATIONS RESEARCH LETTERS, 2017, 45 (02) : 115 - 118
[20] The Euclidean Degree-4 Minimum Spanning Tree Problem is NP-hard
Francke, Andrea
Hoffmann, Michael
PROCEEDINGS OF THE TWENTY-FIFTH ANNUAL SYMPOSIUM ON COMPUTATIONAL GEOMETRY (SCG'09), 2009, : 179 - 188

← 1 2 3 4 5 →