Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
 
 
DownloadE-Mail
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  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

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-25C1-0 Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-25C2-E
Genre: Zeitschriftenartikel

Externe Referenzen

einblenden:

Urheber

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

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: 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

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2005-11-092005
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: Expertenbegutachtung
 Identifikatoren: eDoc: 279202
Anderer: Local-ID: C1256428004B93B8-C90DA7D9684C7004C1256F950021EE6E-AFHKRS05
 Art des Abschluß: -

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Operations Research Letters
Genre der Quelle: Zeitschrift
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: 33 Artikelnummer: - Start- / Endseite: 115 - 120 Identifikator: ISSN: 0167-6377