28559 articles – 22057 Notices  [english version]

inria-00001242, version 1

Approximating k-hop minimum-spanning trees

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