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 journalArticlepeer-review

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 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