MPI-INF D1 Publications: Journal Article: Approximating k-Hop Minimum-Spanning Trees

Journal Article
@Article
Artikel in Fachzeitschrift

Show entries of:

this year (2020) | last year (2019) | two years ago (2018) | Notes URL

Action:

Options:

Goto entry point

Author, Editor(s)

Author(s):

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

dblp
dblp
dblp
dblp
dblp
dblp

Not MPG Author(s):

Har-Peled, Sariel
Könemann, Jochen
Ramos, Edgar A.

BibTeX cite key*:

AFHKRS05

Title

Title*:

Approximating k-Hop Minimum-Spanning Trees

Journal

Journal Title*:	Operations Research Letters	Journal's URL:	http://www.sciencedirect.com/science/journal/01676377
Download URL for the article:		Language:	English

Publisher

Publisher's Name:	Elsevier	Publisher's URL:	http://www.elsevier.com
Publisher's Address:	Amsterdam, The Netherlands	ISSN:	0167-6377

Vol, No, pp, Date

Volume*:	33	Number:	2
Publishing Date:	March 2005
Pages*:	115-120	Number of VG Pages:
Page Start:		Page End:
Sequence Number:		DOI:

Note:
(LaTeX) Abstract:	In this paper we consider the problem of computing minimum-cost spanning trees with depth restrictions. Specifically, we are given an $n$-node complete graph $G$, a metric cost-function $c$ on its edges, and an integer $k\geq 1$. The goal in the minimum-cost $k$-hop spanning tree problem is to compute a spanning tree $T$ in $G$ of minimum total cost such that the longest root-leaf-path in the tree has at most $k$ edges. Our main result is an algorithm that computes a tree of depth at most $k$ and total expected cost $O(\log n)$ times that of a minimum-cost $k$-hop spanning-tree. The result is based upon earlier work on metric space approximation due to Fakcharoenphol et al.[FRT03] and Bartal [Bart96,Bart98]. In particular we show that the problem can be solved exactly in polynomial time when the cost metric $c$ is induced by a so-called hierarchically well-separated tree.
URL for the Abstract:
Categories, Keywords:	Operations Research, Combinatorial Optimization
HyperLinks / References / URLs:
Copyright Message:
Personal Comments:
Download Access Level:	Intranet

Correlation

MPG Unit:	Max-Planck-Institut für Informatik

MPG Subunit:	Algorithms and Complexity Group
Appearance:	MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@ARTICLE{AFHKRS05,
AUTHOR = {Althaus, Ernst and Funke, Stefan and Har-Peled, Sariel and K{\"o}nemann, Jochen and Ramos, Edgar A. and Skutella, Martin},
TITLE = {Approximating k-Hop Minimum-Spanning Trees},
JOURNAL = {Operations Research Letters},
PUBLISHER = {Elsevier},
YEAR = {2005},
NUMBER = {2},
VOLUME = {33},
PAGES = {115--120},
ADDRESS = {Amsterdam, The Netherlands},
MONTH = {March},
ISBN = {0167-6377},
}

Entry last modified by Christine Kiesel, 11/09/2005

Edit History (please click the blue arrow to see the details)

	Editor(s) Stefan Funke	Created 01/26/2005 07:10:37 AM
Revisions 3. 2. 1. 0.	Editor(s) Christine Kiesel Christine Kiesel Christine Kiesel Stefan Funke	Edit Dates 09.11.2005 14:46:34 30.05.2005 15:53:32 30.05.2005 15:28:04 01/26/2005 07:10:37 AM