Veröffentlichung

Titel:

Colored Non-Crossing Euclidean Steiner Forest

AutorInnen:

Sergey Bereg
Krzysztof Fleszar
Philipp Kindermann
Sergey Pupyrev
Joachim Spoerhase
Alexander Wolff

Kategorie:

Konferenzbandbeiträge

erschienen in:

Proceedings of the 26th International Symposium on Algorithms and Computation (ISAAC'15), pp. 429-441

Abstract:

Given a set of k-colored points in the plane, we consider the problem of finding k trees such that each tree connects all points of one color class, no two trees cross, and the total edge length of the trees is minimized. For k=1, this is the well-known Euclidean Steiner tree problem. For general k, a kρ-approximation algorithm is known, where ρ≤1.21 is the Steiner ratio.

We present a PTAS for k=2, a (5/3+ε)-approximation for k=3, and two approximation algorithms for general k, with ratios O(√n log k) and k+ε.

Download:

Springer

BibTeX-Eintrag:

@InProceedings{BFKPSW15, Title = {Colored Non-Crossing Euclidean Steiner Forest}, Author = {Sergey Bereg and Krzysztof Fleszar and Philipp Kindermann and Sergey Pupyrev and Joachim Spoerhase and Alexander Wolff}, Booktitle = {Proceedings of the 26th International Symposium on Algorithms and Computation (ISAAC'15)}, Year = {2015}, Editor = {Khaled M. Elbassioni and Kazuhisa Makino}, Pages = {429--441}, Publisher = {Springer}, Series = {Lecture Notes in Computer Science}, Volume = {9472}, Abstract = {Given a set of $k$-colored points in the plane, we consider the problem of finding $k$ trees such that each tree connects all points of one color class, no two trees cross, and the total edge length of the trees is minimized. For $k=1$, this is the well-known Euclidean Steiner tree problem. For general $k$, a $k\rho$-approximation algorithm is known, where $\rho \le 1.21$ is the Steiner ratio. We present a PTAS for $k=2$, a $(5/3+\varepsilon)$-approximation for $k=3$, and two approximation algorithms for general $k$, with ratios $O(\sqrt n \log k)$ and $k+\varepsilon$.}, Doi = {10.1007/978-3-662-48971-0_37} }