A polynomial algorithm for a constrained traveling salesman problem

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

doi:10.1002/net.1025

A polynomial algorithm for a constrained traveling salesman problem

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

Research output: Contribution to journal › Article › Research › peer-review

3 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 language	English
Pages (from-to)	68-75
Number of pages	8
Journal	Networks
Volume	38
Issue number	2
DOIs	https://doi.org/10.1002/net.1025
Publication status	Published - Sep 2001
Externally published	Yes

Keywords

Euclidean traveling salesman problem
Polynomial algorithm
Traveling salesman problem

Access to Document

10.1002/net.1025

Cite this

@article{1cfe95c042344d4d92b9e32619bb22fa,

title = "A polynomial algorithm for a constrained traveling salesman problem",

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.",

keywords = "Euclidean traveling salesman problem, Polynomial algorithm, Traveling salesman problem",

author = "Rubinstein, {J. H.} and Thomas, {D. A.} and Wormald, {N. C.}",

year = "2001",

month = sep,

doi = "10.1002/net.1025",

language = "English",

volume = "38",

pages = "68--75",

journal = "Networks",

issn = "0028-3045",

publisher = "Wiley-Blackwell",

number = "2",

}

TY - JOUR

T1 - A polynomial algorithm for a constrained traveling salesman problem

AU - Rubinstein, J. H.

AU - Thomas, D. A.

AU - Wormald, N. C.

PY - 2001/9

Y1 - 2001/9

N2 - 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.

AB - 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.

KW - Euclidean traveling salesman problem

KW - Polynomial algorithm

KW - Traveling salesman problem

UR - http://www.scopus.com/inward/record.url?scp=0035637899&partnerID=8YFLogxK

U2 - 10.1002/net.1025

DO - 10.1002/net.1025

M3 - Article

AN - SCOPUS:0035637899

VL - 38

SP - 68

EP - 75

JO - Networks

JF - Networks

SN - 0028-3045

IS - 2

ER -

A polynomial algorithm for a constrained traveling salesman problem

Abstract

Keywords

Access to Document

Other files and links

Cite this