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