Journal
JOURNAL OF COMBINATORIAL OPTIMIZATION
Volume 4, Issue 2, Pages 187-195Publisher
SPRINGER
DOI: 10.1023/A:1009846620554
Keywords
Steiner tree; computational complexity
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available