On the complexity of the Steiner problem

DOI10.1023/A:1009846620554zbMATH Open1028.90045OpenAlexW1539131923MaRDI QIDQ1583698FDOQ1583698

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

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

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)

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
• Title not available (Why is that?)
• Computational complexity of the 2-connected Steiner network problem in the \(\ell_p\) plane
• 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)