The Rectilinear Steiner Arborescence Problem Is NP-Complete

DOI10.1137/S0097539704371353MaRDI QIDQ5470711zbMATH OpenOpenAlexFDO

Authors Weiping Shi, Chen Su

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

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

Recommendations

• scientific article; zbMATH DE number 1445377
• The rectilinear Steiner arborescence problem
• Polynomial time approximation scheme for the rectilinear Steiner arborescence problem
• Subclass of the Steiner problems on a plane with rectilinear metric
• Subexponential algorithms for rectilinear Steiner tree and arborescence problems

Cited in

(16)

• The rectilinear Steiner arborescence problem
• Polynomial time approximation scheme for the rectilinear Steiner arborescence problem
• Swap-vertex based neighborhood for Steiner tree problems
• Approximating the generalized minimum Manhattan network problem
• Polynomial time approximation scheme for symmetric rectilinear Steiner arborescence 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
• Embedding rectilinear Steiner trees with length restrictions
• Steiner trees with bounded RC-delay
• scientific article; zbMATH DE number 1445377 (Why is no real title available?)
• Steiner trees with bounded RC-delay
• Dynamic programming approach to the generalized minimum Manhattan network problem
• Precedence-constrained arborescences
• Linear planar 3-SAT
• Linear-size planar Manhattan network for convex point sets

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5470711)