3543 articles – 5273 references  [version française]

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

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.

  • 1:  MODBIO (INRIA Lorraine - LORIA)
  • INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)
  • Comment : http://www.sciencedirect.com
 
  • inria-00001242, version 1
  • http://hal.inria.fr/inria-00001242
  • oai:hal.inria.fr:inria-00001242
  • From: Publications Loria <>
  • Submitted on: Tuesday, 11 April 2006 16:44:35
  • Updated on: Wednesday, 10 January 2007 15:11:30