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 条

[31] Euclidean Bottleneck Bounded-Degree Spanning Tree Ratios
Ahmad Biniaz
Discrete & Computational Geometry, 2022, 67 : 311 - 327
[32] Bounded-degree minimum-radius spanning trees in wireless sensor networks
An, Min Kyung
Lam, Nhat X.
Huynh, Dung T.
Nguyen, Trac N.
THEORETICAL COMPUTER SCIENCE, 2013, 498 : 46 - 57
[33] The label-constrained minimum spanning tree problem
Xiong, Yupei
Golden, Bruce
Wasil, Edward
Chen, Si
TELECOMMUNICATIONS MODELING, POLICY, AND TECHNOLOGY, 2008, : 39 - +
[34] AN EXACT METHOD FOR SOLVING THE BI-OBJECTIVE MINIMUM DIAMETER-COST SPANNING TREE PROBLEM
De Sousa, Ernando Gomes
Santos, Andrea Cynthia
Aloise, Dario Jose
RAIRO-OPERATIONS RESEARCH, 2015, 49 (01) : 143 - 160
[35] Scatter search for the minimum leaf spanning tree problem
Kardam, Yogita Singh
Srivastava, Kamal
Jain, Pallavi
Marti, Rafael
COMPUTERS & OPERATIONS RESEARCH, 2022, 145
[36] Bounded-degree spanning tree problems: models and new algorithms
Cerulli, R.
Gentili, M.
Iossa, A.
COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 2009, 42 (03) : 353 - 370
[37] Bounded-degree spanning tree problems: models and new algorithms
R. Cerulli
M. Gentili
A. Iossa
Computational Optimization and Applications, 2009, 42 : 353 - 370
[38] ADDITIVE GUARANTEES FOR DEGREE-BOUNDED DIRECTED NETWORK DESIGN
Bansal, Nikhil
Khandekar, Rohit
Nagarajan, Viswanath
SIAM JOURNAL ON COMPUTING, 2009, 39 (04) : 1413 - 1431
[39] The Stackelberg Minimum Spanning Tree Game
Jean Cardinal
Erik D. Demaine
Samuel Fiorini
Gwenaël Joret
Stefan Langerman
Ilan Newman
Oren Weimann
Algorithmica, 2011, 59 : 129 - 144
[40] The Stackelberg Minimum Spanning Tree Game
Cardinal, Jean
Demaine, Erik D.
Fiorini, Samuel
Joret, Gwenael
Langerman, Stefan
Newman, Ilan
Weimann, Oren
ALGORITHMICA, 2011, 59 (02) : 129 - 144

← 1 2 3 4 5 →