HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

Approximating $k$-hop minimum-spanning trees

Abstract : Given a complete graph on~$n$ nodes with metric edge costs, the minimum-cost k-hop spanning tree ($k$HMST) 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 $O(log n)$ times that of a minimum-cost $k$-hop spanning-tree.
Document type :
Journal articles
Complete list of metadata

https://hal.inria.fr/inria-00001242
Contributor : Publications Loria Connect in order to contact the contributor
Submitted on : Tuesday, April 11, 2006 - 4:44:35 PM
Last modification on : Friday, March 4, 2022 - 3:02:07 PM

Links full text

Identifiers

Collections

Citation

Ernst Althaus, Stefan Funke, Sariel Har-Peled, Jochen Könemann, Edgar Ramos, et al.. Approximating $k$-hop minimum-spanning trees. Operations Research Letters, Elsevier, 2005, 33 (2), pp.115-120. ⟨10.1016/j.orl.2004.05.005⟩. ⟨inria-00001242⟩

Share

Metrics

Record views

57