An asymmetric analogue of van der Veen conditions and the traveling salesman problem

Yoshiaki Oda

doi:10.1016/S0166-218X(00)00273-0

An asymmetric analogue of van der Veen conditions and the traveling salesman problem

Yoshiaki Oda

Department of Mathematics

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

5 Citations (Scopus)

Abstract

In (J.A.A. van der Veen, SIAM J. Discrete Math, 7, 1994, 585-592), van der Veen proved that for the traveling salesman problem which satisfies some symmetric conditions (called van der Veen conditions) a shortest pyramidal tour is optimal. From this fact, an optimal tour can be computed in polynomial time. In this paper, we prove that a class satisfying an asymmetric analogue of van der Veen conditions is polynomially solvable. An optimal tour of the instance in this class forms a tour which is an extension of pyramidal ones.

Original language	English
Pages (from-to)	279-292
Number of pages	14
Journal	Discrete Applied Mathematics
Volume	109
Issue number	3
DOIs	https://doi.org/10.1016/S0166-218X(00)00273-0
Publication status	Published - 2001 May 15

Keywords

A pyramidal tour
Polynomially solvable classes
The traveling salesman problem

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/S0166-218X(00)00273-0

Cite this

@article{121348b7476149118096e062d560d0cc,

title = "An asymmetric analogue of van der Veen conditions and the traveling salesman problem",

abstract = "In (J.A.A. van der Veen, SIAM J. Discrete Math, 7, 1994, 585-592), van der Veen proved that for the traveling salesman problem which satisfies some symmetric conditions (called van der Veen conditions) a shortest pyramidal tour is optimal. From this fact, an optimal tour can be computed in polynomial time. In this paper, we prove that a class satisfying an asymmetric analogue of van der Veen conditions is polynomially solvable. An optimal tour of the instance in this class forms a tour which is an extension of pyramidal ones.",

keywords = "A pyramidal tour, Polynomially solvable classes, The traveling salesman problem",

author = "Yoshiaki Oda",

note = "Funding Information: The author would like to thank Professor H. Enomoto for his helpful suggestions and the referee for his careful reading and appropriate comments and advice. This work was partially supported by JSPS Research Fellowships for Young Scientists and by the Grant in Aid for Scientific Research of the Ministry of Education, Science and Culture of Japan.",

year = "2001",

month = may,

day = "15",

doi = "10.1016/S0166-218X(00)00273-0",

language = "English",

volume = "109",

pages = "279--292",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

number = "3",

}

TY - JOUR

T1 - An asymmetric analogue of van der Veen conditions and the traveling salesman problem

AU - Oda, Yoshiaki

N1 - Funding Information: The author would like to thank Professor H. Enomoto for his helpful suggestions and the referee for his careful reading and appropriate comments and advice. This work was partially supported by JSPS Research Fellowships for Young Scientists and by the Grant in Aid for Scientific Research of the Ministry of Education, Science and Culture of Japan.

PY - 2001/5/15

Y1 - 2001/5/15

N2 - In (J.A.A. van der Veen, SIAM J. Discrete Math, 7, 1994, 585-592), van der Veen proved that for the traveling salesman problem which satisfies some symmetric conditions (called van der Veen conditions) a shortest pyramidal tour is optimal. From this fact, an optimal tour can be computed in polynomial time. In this paper, we prove that a class satisfying an asymmetric analogue of van der Veen conditions is polynomially solvable. An optimal tour of the instance in this class forms a tour which is an extension of pyramidal ones.

AB - In (J.A.A. van der Veen, SIAM J. Discrete Math, 7, 1994, 585-592), van der Veen proved that for the traveling salesman problem which satisfies some symmetric conditions (called van der Veen conditions) a shortest pyramidal tour is optimal. From this fact, an optimal tour can be computed in polynomial time. In this paper, we prove that a class satisfying an asymmetric analogue of van der Veen conditions is polynomially solvable. An optimal tour of the instance in this class forms a tour which is an extension of pyramidal ones.

KW - A pyramidal tour

KW - Polynomially solvable classes

KW - The traveling salesman problem

UR - https://www.scopus.com/pages/publications/0007705353

UR - https://www.scopus.com/pages/publications/0007705353#tab=citedBy

U2 - 10.1016/S0166-218X(00)00273-0

DO - 10.1016/S0166-218X(00)00273-0

M3 - Article

AN - SCOPUS:0007705353

SN - 0166-218X

VL - 109

SP - 279

EP - 292

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 3

ER -

An asymmetric analogue of van der Veen conditions and the traveling salesman problem

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this