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 条

[21] The first approximated distributed algorithm for the Minimum Degree Spanning Tree problem on general graphs
Blin, L
Butelle, F
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2004, 15 (03) : 507 - 516
[22] Minimum Spanning Tree Cycle Intersection problem
Dubinsky, Manuel
Massri, Cesar
Taubin, Gabriel
DISCRETE APPLIED MATHEMATICS, 2021, 294 : 152 - 166
[23] 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
[24] On the complexity of the bilevel minimum spanning tree problem
Buchheim, Christoph
Henke, Dorothee
Hommelsheim, Felix
NETWORKS, 2022, 80 (03) : 338 - 355
[25] Fast reoptimization for the minimum spanning tree problem
Boria, Nicolas
Paschos, Vangelis Th.
JOURNAL OF DISCRETE ALGORITHMS, 2010, 8 (03) : 296 - 310
[26] Approximating the minimum weight spanning tree of a set of points in the Hausdorff metric
Alvarez, Victor
Seidel, Raimund
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2010, 43 (02): : 94 - 98
[27] APPROXIMATING MINIMUM-COST GRAPH PROBLEMS WITH SPANNING TREE EDGES
GOEMANS, MX
WILLIAMSON, DP
OPERATIONS RESEARCH LETTERS, 1994, 16 (04) : 183 - 189
[28] Modeling and solving the bi-objective minimum diameter-cost spanning tree problem
Andréa Cynthia Santos
Diego Rocha Lima
Dario José Aloise
Journal of Global Optimization, 2014, 60 : 195 - 216
[29] Modeling and solving the bi-objective minimum diameter-cost spanning tree problem
Santos, Andrea Cynthia
Lima, Diego Rocha
Aloise, Dario Jose
JOURNAL OF GLOBAL OPTIMIZATION, 2014, 60 (02) : 195 - 216
[30] Euclidean Bottleneck Bounded-Degree Spanning Tree Ratios
Biniaz, Ahmad
DISCRETE & COMPUTATIONAL GEOMETRY, 2022, 67 (01) : 311 - 327

← 1 2 3 4 5 →