Approximating k-hop minimum-spanning trees

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

doi:10.1016/j.orl.2004.05.005

Approximating k-hop minimum-spanning trees

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

Siebel School of Computing and Data Science

Research output: Contribution to journal › Article › peer-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 language	English (US)
Pages (from-to)	115-120
Number of pages	6
Journal	Operations Research Letters
Volume	33
Issue number	2
DOIs	https://doi.org/10.1016/j.orl.2004.05.005
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

Online availability

10.1016/j.orl.2004.05.005

Library availability

Discover UIUC Full Text

Cite this

@article{8ffea60f544e47e0a5d9579a599bbd7a,

title = "Approximating k-hop minimum-spanning trees",

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.",

keywords = "Approximation algorithms, Depth restriction, Metric space approximation, Minimum spanning trees",

author = "Ernst Althaus and Stefan Funke and Sariel Har-Peled and Jochen K{\"o}nemann and Ramos, {Edgar A.} and Martin Skutella",

note = "Funding Information: We would like to thank an anonymous referee for many helpful comments and pointers to the literature. This work was supported in part by the IST Program of the EU under contract numbers IST-1999-14186 (ALCOM-FT) and IST-2001-30012 (APPOL II). Copyright: Copyright 2008 Elsevier B.V., All rights reserved.",

year = "2005",

month = mar,

doi = "10.1016/j.orl.2004.05.005",

language = "English (US)",

volume = "33",

pages = "115--120",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "2",

}

TY - JOUR

T1 - Approximating k-hop minimum-spanning trees

AU - Althaus, Ernst

AU - Funke, Stefan

AU - Har-Peled, Sariel

AU - Könemann, Jochen

AU - Ramos, Edgar A.

AU - Skutella, Martin

N1 - Funding Information: We would like to thank an anonymous referee for many helpful comments and pointers to the literature. This work was supported in part by the IST Program of the EU under contract numbers IST-1999-14186 (ALCOM-FT) and IST-2001-30012 (APPOL II). Copyright: Copyright 2008 Elsevier B.V., All rights reserved.

PY - 2005/3

Y1 - 2005/3

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

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

KW - Approximation algorithms

KW - Depth restriction

KW - Metric space approximation

KW - Minimum spanning trees

UR - http://www.scopus.com/inward/record.url?scp=9644254523&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=9644254523&partnerID=8YFLogxK

U2 - 10.1016/j.orl.2004.05.005

DO - 10.1016/j.orl.2004.05.005

M3 - Article

AN - SCOPUS:9644254523

SN - 0167-6377

VL - 33

SP - 115

EP - 120

JO - Operations Research Letters

JF - Operations Research Letters

IS - 2

ER -

Approximating k-hop minimum-spanning trees

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this