Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/102318
Title: Colored non-crossing Euclidean Steiner forest
Authors: Bereg, S.
Fleszar, K.
Kindermann, P.
Pupyrev, S.
Spoerhase, J.
Wolff, A.
Issue Date: 2015
Publisher: Springer Verlag
Citation: Colored non-crossing Euclidean Steiner forest / S. Bereg, K. Fleszar, P. Kindermann, et al. — DOI 10.1007/978-3-662-48971-0_37 // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). — 2015. — Vol. 9472. — P. 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 + ε. © Springer-Verlag Berlin Heidelberg 2015.
Keywords: ALGORITHMS
EDGE LENGTH
EUCLIDEAN
EUCLIDEAN STEINER TREE PROBLEMS
K-TREES
STEINER FORESTS
STEINER RATIO
APPROXIMATION ALGORITHMS
URI: http://hdl.handle.net/10995/102318
Access: info:eu-repo/semantics/openAccess
SCOPUS ID: 84952045448
PURE ID: 567340
fe0e1de0-1723-4d16-bcb3-abdd7b114ef4
ISSN: 3029743
ISBN: 9783662489703
DOI: 10.1007/978-3-662-48971-0_37
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
2-s2.0-84952045448.pdf392,32 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.