English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 Local TagsRelease HistoryDetailsSummary
  Approximating k-Hop Minimum-Spanning Trees

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, 115-120.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-25C1-0 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-25C2-E
Genre: Journal Article

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Althaus, Ernst1, Author           
Funke, Stefan1, Author           
Har-Peled, Sariel, Author
Könemann, Jochen1, Author           
Ramos, Edgar A.1, Author           
Skutella, Martin1, Author           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 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.

Details

show
hide
Language(s): eng - English
 Dates: 2005-11-092005
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: Peer
 Identifiers: eDoc: 279202
Other: Local-ID: C1256428004B93B8-C90DA7D9684C7004C1256F950021EE6E-AFHKRS05
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: Operations Research Letters
Source Genre: Journal
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 33 Sequence Number: - Start / End Page: 115 - 120 Identifier: ISSN: 0167-6377