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 language | English (US) |
---|---|
Pages (from-to) | 115-120 |
Number of pages | 6 |
Journal | Operations Research Letters |
Volume | 33 |
Issue number | 2 |
DOIs | |
State | Published - 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