%0 Conference Paper %1 bfkpsw-cnesf-isaac15 %A Bereg, Sergey %A Fleszar, Krzysztof %A Kindermann, Philipp %A Pupyrev, Sergey %A Spoerhase, Joachim %A Wolff, Alexander %B Proceedings of the 26th International Symposium on Algorithms and Computation (ISAAC'15) %D 2015 %E Elbassioni, Khaled %E Makino, Kazuhisa %I Springer-Verlag %K Steiner colored forest myown noncrossing %P 429--441 %R 10.1007/978-3-662-48971-0_37 %T Colored Non-Crossing Euclidean Steiner Forest %V 9472 %X 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 $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(n k)$ and $k+\varepsilon$.

@inproceedings{bfkpsw-cnesf-isaac15, 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$.}, added-at = {2015-09-10T15:07:27.000+0200}, arxiv = {https://arxiv.org/abs/1509.05681}, author = {Bereg, Sergey and Fleszar, Krzysztof and Kindermann, Philipp and Pupyrev, Sergey and Spoerhase, Joachim and Wolff, Alexander}, biburl = {https://www.bibsonomy.org/bibtex/277b92ff9654fceef9bfe332bfb877fe3/kindermann}, booktitle = {Proceedings of the 26th International Symposium on Algorithms and Computation (ISAAC'15)}, doi = {10.1007/978-3-662-48971-0_37}, editor = {Elbassioni, Khaled and Makino, Kazuhisa}, interhash = {00c401f11645ab9627e5c508d055dfba}, intrahash = {77b92ff9654fceef9bfe332bfb877fe3}, keywords = {Steiner colored forest myown noncrossing}, month = dec, pages = {429--441}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, slides = {http://www1.pub.informatik.uni-wuerzburg.de/pub/kindermann/slides/2015-isaac-coloredsteiner.pdf}, timestamp = {2018-09-18T07:15:58.000+0200}, title = {Colored Non-Crossing Euclidean Steiner Forest}, volume = 9472, year = 2015 }