The Rectilinear Steiner Arborescence Problem Is NP-Complete

DOI10.1137/S0097539704371353zbMath1095.68039OpenAlexW2150488380MaRDI QIDQ5470711

Chen Su, Weiping Shi

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

zbMATH Keywords

computational complexityNP-completenessSteiner tree

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (11)

Linear-size planar Manhattan network for convex point sets ⋮ Steiner Trees with Bounded RC-Delay ⋮ Embedding rectilinear Steiner trees with length restrictions ⋮ The Rectilinear Steiner Tree Problem with Given Topology and Length Restrictions ⋮ Precedence-constrained arborescences ⋮ Swap-vertex based neighborhood for Steiner tree problems ⋮ Regular Language Constrained Sequence Alignment Revisited ⋮ Approximating the generalized minimum Manhattan network problem ⋮ Steiner trees with bounded RC-delay ⋮ Dynamic programming approach to the generalized minimum Manhattan network problem ⋮ Angle-restricted Steiner arborescences for flow map layout

This page was built for publication: The Rectilinear Steiner Arborescence Problem Is NP-Complete