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 条
12345