Colored Non-crossing Euclidean Steiner Forest
作者： Sergey Bereg , Krzysztof Fleszar , Philipp Kindermann , Sergey Pupyrev , Joachim Spoerhase
DOI: 10.1007/978-3-662-48971-0_37
关键词:
摘要: Given a set of k-colored points in the plane, we consider problem finding k trees such that each tree connects all one color class, no two cross, and total edge length is minimized. For \(k = 1\), this well-known Euclidean Steiner problem. general k, \(k\rho \)-approximation algorithm known, where \(\rho \le 1.21\) ratio.
springer.com
mpg.de
harvard.edu
arxiv.org
sci-hub.st 参考文章(18)
Alon Efrat, Yifan Hu, Stephen G Kobourov, Sergey Pupyrev, None, MapSets: Visualizing Embedded and Clustered Graphs graph drawing. ,vol. 8871, pp. 452- 463 ,(2014) , 10.1007/978-3-662-45803-7_38
Yoshiyuki Kusakari, Daisuke Masubuchi, Takao Nishizeki, Finding a Noncrossing Steiner Forest in Plane Graphs Under a 2-Face Condition Journal of Combinatorial Optimization. ,vol. 5, pp. 249- 266 ,(2001) , 10.1023/A:1011425821069
Kevin Verbeek, Homotopic C -oriented routing graph drawing. pp. 272- 278 ,(2012) , 10.1007/978-3-642-36763-2_24
Joseph S.B. Mitchell, Chapter 15 – Geometric Shortest Paths and Network Optimization Handbook of Computational Geometry. pp. 633- 701 ,(2000) , 10.1016/B978-044482537-7/50016-4
Joseph S. B. Mitchell, Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k -MST, and Related Problems SIAM Journal on Computing. ,vol. 28, pp. 1298- 1309 ,(1999) , 10.1137/S0097539796309764
Amir Nayyeri, Jeff Erickson, Shortest non-crossing walks in the plane symposium on discrete algorithms. pp. 297- 308 ,(2011) , 10.5555/2133036.2133061
Alon Efrat, Stephen G. Kobourov, Anna Lubiw, Computing homotopic shortest paths efficiently Computational Geometry: Theory and Applications. ,vol. 35, pp. 162- 172 ,(2006) , 10.1016/J.COMGEO.2006.03.003
Michael R. Garey, David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness ,(1979)
Glencora Borradaile, Philip Klein, Claire Mathieu, An
O
(
n
log
n
) approximation scheme for Steiner tree in planar graphs ACM Transactions on Algorithms. ,vol. 5, pp. 1- 31 ,(2009) , 10.1145/1541885.1541892
Matthias Müller-Hannemann, Siamak Tazari, A near linear time approximation scheme for Steiner tree among obstacles in the plane Computational Geometry. ,vol. 43, pp. 395- 409 ,(2010) , 10.1016/J.COMGEO.2009.01.011