|
|||||
|
|
Approximating the Degree-Bounded Minimum Diameter Spanning Tree Problem |
|
| Authors: | Jochen Könemann Asaf Levin and 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 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. |
| Keywords: | Approximation algorithms Spanning trees Bicriteria approximation Degree-bounded spanning trees |
| 本文献已被 SpringerLink 等数据库收录！ | |