On the complexity of the Steiner problem

DOI10.1023/A:1009846620554MaRDI QIDQ1583698zbMATH OpenOpenAlexFDO

Authors M. Brazil, D. A. Thomas, J. F. Weng

Publication date 30 October 2000

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1023/a:1009846620554

zbMATH Keywords

computational complexitySteiner tree

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• The Steiner problem with edge lengths 1 and 2
• Subclass of the Steiner problems on a plane with rectilinear metric
• On the structure and complexity of the 2-connected Steiner network problem in the plane
• The Steiner tree problem
• Polynomially solvable special cases of the Steiner problem in planar networks

Cited in

(10)

• On the approximability of dense Steiner problems
• Minimum Steiner trees on a set of concyclic points and their center
• Solving the prize‐collecting Euclidean Steiner tree problem
• On the restricted 1-Steiner tree problem
• On the restricted \(k\)-Steiner tree problem
• Structural properties of minimum multi-source multi-sink Steiner networks in the Euclidean plane
• THE UNIFORM ORIENTATION STEINER TREE PROBLEM IS NP-HARD
• Computational complexity of the 2-connected Steiner network problem in the \(\ell_p\) plane
• scientific article; zbMATH DE number 1424546 (Why is no real title available?)
• A note on computational aspects of the Steiner traveling salesman problem

This page was built for publication: On the complexity of the Steiner problem

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