Steiner trees for terminals constrained to curves

J. H. Rubinstein, D. A. Thomas, N. C. Wormald

Research output: Contribution to journalArticleResearchpeer-review

11 Citations (Scopus)

Abstract

We give a polynomial time algorithm for solving the Euclidean Steiner tree problem when the terminals are constrained to lie on a fixed finite set of disjoint finite-length compact simple smooth curves. The problem is known to be NP-hard in general. We also show it to be NP-hard if the terminals lie on two parallel infinite lines or on a bent line segment provided the bend has an angle of less than 120°.

Original languageEnglish
Pages (from-to)1-17
Number of pages17
JournalSIAM Journal on Discrete Mathematics
Volume10
Issue number1
DOIs
Publication statusPublished - 1997
Externally publishedYes

Keywords

  • Polynomial algorithms
  • Steiner trees

Cite this