|
|||||
|
|
Approximating the Degree-Bounded Minimum Diameter Spanning Tree Problem |
|
| Authors: | Jochen Kö nemann, Asaf Levin Amitabh Sinha |
| Affiliation: | (1) Department of Combinatorics and Optimization, University of Waterloo, 200 University Avenue West, Waterloo, Ontario, N2L 3G1, Canada;(2) Faculty of Industrial Engineering and Management, The Technion, Haifa 32000, Israel;(3) Business School, University of Michigan, Ann Arbor, MI 48103, USA |
| Abstract: | We consider the problem of finding a minimum diameter spanning treewith maximum node degree $B$ in a complete undirected edge-weightedgraph. We provide an $O(sqrt{log_Bn})$-approximation algorithm for theproblem. Our algorithm is purely combinatorial, and relies on acombination of filtering and divide and conquer. |
| Keywords: | Approximation algorithms Spanning trees Bicriteria approximation Degree-bounded spanning trees |
| 本文献已被 SpringerLink 等数据库收录！ | |