Skip to Main content Skip to Navigation
Journal articles

Approximating k-hop minimum-spanning trees

Ernst Althaus 1 Stefan Funke Sariel Har-Peled Jochen Könemann Edgar A. Ramos Martin Skutella
1 MODBIO - Computational models in molecular biology
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : Given a complete graph on~n nodes with metric edge costs, the minimum-cost k-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 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 <>
Submitted on : Tuesday, April 11, 2006 - 4:44:35 PM
Last modification on : Friday, February 26, 2021 - 3:28:05 PM

Identifiers

Collections

Citation

Ernst Althaus, Stefan Funke, Sariel Har-Peled, Jochen Könemann, Edgar A. 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

165