Name
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 <= 1.21 is the Steiner ratio. We present a PTAS for k = 2, a (5/3 + epsilon)-approximation for k = 3, and two approximation algorithms for general k, with ratios O(root n log k) and k + epsilon. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1007/978-3-662-48971-0_37 | ALGORITHMS AND COMPUTATION, ISAAC 2015 |
DocType | Volume | ISSN |
Conference | 9472 | 0302-9743 |
Citations | PageRank | References |
2 | 0.46 | 16 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sergey Bereg | 1 | 245 | 40.81 |
| Krzysztof Fleszar | 2 | 368 | 25.38 |
| Philipp Kindermann | 3 | 63 | 11.87 |
| Sergey Pupyrev | 4 | 148 | 17.77 |
| Joachim Spoerhase | 5 | 112 | 14.12 |
| Alexander Wolff | 6 | 222 | 22.66 |