The Rectilinear Steiner Tree Problem is $NP$-Complete
- 1 June 1977
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Applied Mathematics
- Vol. 32 (4), 826-834
- https://doi.org/10.1137/0132071
Abstract
No abstract availableThis publication has 12 references indexed in Scilit:
- Rectilinear steiner trees: Efficient special-case algorithmsNetworks, 1977
- Some simplified NP-complete graph problemsTheoretical Computer Science, 1976
- On Steiner Minimal Trees with Rectilinear DistanceSIAM Journal on Applied Mathematics, 1976
- Efficient Planarity TestingJournal of the ACM, 1974
- The Generation of Minimal Trees with a Steiner TopologyJournal of the ACM, 1972
- A Counterexample to a Theorem of Fu on Steiner's ProblemIEEE Transactions on Circuit Theory, 1972
- Steiner's problem in graphs and its implicationsNetworks, 1971
- The steiner problem in graphsNetworks, 1971
- Steiner Minimal TreesSIAM Journal on Applied Mathematics, 1968
- On Steiner’s Problem with Rectilinear DistanceSIAM Journal on Applied Mathematics, 1966