On the complexity of the Steiner problem

DOI10.1023/A:1009846620554zbMath1028.90045OpenAlexW1539131923MaRDI QIDQ1583698

Doreen Anne Thomas, Jia Feng Weng, Marcus Brazil

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

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

Related Items (6)

THE UNIFORM ORIENTATION STEINER TREE PROBLEM IS NP-HARD ⋮ Minimum Steiner trees on a set of concyclic points and their center ⋮ Solving the prize‐collecting Euclidean Steiner tree problem ⋮ Structural properties of minimum multi-source multi-sink Steiner networks in the Euclidean plane ⋮ On the restricted 1-Steiner tree problem ⋮ On the restricted \(k\)-Steiner tree problem

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