On the Complexity of the Steiner Problem

M. Brazil, D.A. Thomas and J.F. Weng
Additional contact information
M. Brazil: The University of Melbourne
D.A. Thomas: The University of Melbourne
J.F. Weng: The University of Melbourne

Journal of Combinatorial Optimization, 2000, vol. 4, issue 2, No 3, 187-195

Abstract: Abstract Recently Rubinstein et al. gave a new proof of the NP-completeness of the discretized Steiner problem, that is, the problem of finding a shortest network connecting a given set of points in the plane where all vertices are integer points and a discretized metric is used. Their approach was to consider the complexity of the PALIMEST problem, the Steiner problem for sets of points lying on two parallel lines. In this paper, we give a new proof of this theorem, using simpler, more constructive arguments. We then extend the result to a more general class of networks known as APE-Steiner trees in which certain angles between edges or slopes of edges are specified beforehand.

Keywords: Steiner tree; computational complexity (search for similar items in EconPapers)
Date: 2000
References: View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1023/A:1009846620554 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:4:y:2000:i:2:d:10.1023_a:1009846620554

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1023/A:1009846620554

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().