A polynomial algorithm for a constrained traveling salesman problem

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

Research output: Contribution to journalArticleResearchpeer-review

2 Citations (Scopus)

Abstract

We give a polynomial-time algorithm for finding a solution to the Traveling Salesman Problem when the points given are constrained to lie on a fixed set of smooth curves of finite length.

Original languageEnglish
Pages (from-to)68-75
Number of pages8
JournalNetworks
Volume38
Issue number2
DOIs
Publication statusPublished - Sep 2001
Externally publishedYes

Keywords

  • Euclidean traveling salesman problem
  • Polynomial algorithm
  • Traveling salesman problem

Cite this