The Rectilinear Steiner Arborescence Problem Is NP-Complete
From MaRDI portal
Publication:5470711
DOI10.1137/S0097539704371353zbMath1095.68039MaRDI QIDQ5470711
Publication date: 1 June 2006
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539704371353
90C27: Combinatorial optimization
68U05: Computer graphics; computational geometry (digital and algorithmic aspects)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Dynamic programming approach to the generalized minimum Manhattan network problem, Precedence-constrained arborescences, Embedding rectilinear Steiner trees with length restrictions, Steiner trees with bounded RC-delay, Linear-size planar Manhattan network for convex point sets, Swap-vertex based neighborhood for Steiner tree problems, Approximating the generalized minimum Manhattan network problem, Angle-restricted Steiner arborescences for flow map layout, Regular Language Constrained Sequence Alignment Revisited, The Rectilinear Steiner Tree Problem with Given Topology and Length Restrictions, Steiner Trees with Bounded RC-Delay