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 - http://www.scopus.com/inward/record.url?scp=0007705353&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0007705353&partnerID=8YFLogxK
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 -