Approximating k-hop minimum-spanning trees

Ernst Althaus, Stefan Funke, Sariel Har-Peled, Jochen Könemann, Edgar A. Ramos, Martin Skutella

Research output: Contribution to journalArticle

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.

Original languageEnglish (US)
Pages (from-to)115-120
Number of pages6
JournalOperations Research Letters
Volume33
Issue number2
DOIs
StatePublished - Mar 1 2005

Keywords

  • Approximation algorithms
  • Depth restriction
  • Metric space approximation
  • Minimum spanning trees

ASJC Scopus subject areas

  • Software
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Approximating k-hop minimum-spanning trees'. Together they form a unique fingerprint.

  • Cite this

    Althaus, E., Funke, S., Har-Peled, S., Könemann, J., Ramos, E. A., & Skutella, M. (2005). Approximating k-hop minimum-spanning trees. Operations Research Letters, 33(2), 115-120. https://doi.org/10.1016/j.orl.2004.05.005