×

Colored non-crossing Euclidean Steiner forest. (English) Zbl 1472.68109

Elbassioni, Khaled (ed.) et al., Algorithms and computation. 26th international symposium, ISAAC 2015, Nagoya, Japan, December 9–11, 2015. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 9472, 429-441 (2015).
Summary: 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 \leq 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 \).
For the entire collection see [Zbl 1326.68015].

MSC:

68R10 Graph theory (including graph drawing) in computer science
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68W25 Approximation algorithms
PDFBibTeX XMLCite
Full Text: DOI arXiv