inria-00001242, version 1
Approximating k-hop minimum-spanning trees
Ernst Althaus
1Stefan FunkeSariel Har-PeledJochen KönemannEdgar A. RamosMartin Skutella
Operations Research Letters 33, 2 (2005) 115-120
Résumé : 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.
- 1 : MODBIO (INRIA Lorraine - LORIA)
- INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)
- Commentaire : http://www.sciencedirect.com
- inria-00001242, version 1
- http://hal.inria.fr/inria-00001242
- oai:hal.inria.fr:inria-00001242
- Contributeur : Publications Loria
- Soumis le : Mardi 11 Avril 2006, 16:44:35
- Dernière modification le : Mercredi 10 Janvier 2007, 15:11:30
Documents associés
Exporter