|
|||||
|
|
Approximating k-hop minimum-spanning trees |
|
| Authors: | Ernst Althaus Stefan Funke Sariel Har-Peled Edgar A Ramos |
| Institution: | a Université Henri Poincaré, LORIA, B.P. 239, F-54506 Vandoeuvre-lès-Nancy, France b Max-Planck-Institut für Informatik, Stuhlsatzenhausweg 85, 66123 Saarbrücken, Germany c University of Illinois at Urbana-Champaign, USA d Department of Combinatorics and Optimization, University of Waterloo, 200 University Avenue West, Waterloo, Canada ON N2L 3G1 |
| Abstract: | Given a complete graph on~n nodes with metric edge costs, the minimum-costk-hop spanning tree (kHMST) problem asks for a spanning tree of minimum total cost such that the longest root-leaf-path in the tree has at most k edges. We present an algorithm that computes such a tree of total expected cost  times that of a minimum-cost k-hop spanning-tree. |
| Keywords: | Approximation algorithms Minimum spanning trees Depth restriction Metric space approximation |
| 本文献已被 ScienceDirect 等数据库收录！ | |