Pyramidal tours with step-backs and the asymmetric traveling salesman problem

Hikoe Enomoto; Yoshiaki Oda; Katsuhiro Ota

doi:10.1016/S0166-218X(98)00048-1

Pyramidal tours with step-backs and the asymmetric traveling salesman problem

Hikoe Enomoto
, Yoshiaki Oda
, Katsuhiro Ota

数理科学科

研究成果: Article › 査読

11 被引用数 (Scopus)

抄録

In this paper, we introduce the notion of a pyramidal tour with step-backs which is an extension of a pyramidal tour. By using this idea we shall show that for a class of distance matrices an optimal tour of traveling salesman problem can be computed in polynomial time.

本文言語	English
ページ（範囲）	57-65
ページ数	9
ジャーナル	Discrete Applied Mathematics
巻	87
号	1-3
DOI	https://doi.org/10.1016/S0166-218X(98)00048-1
出版ステータス	Published - 1998 10月 5

ASJC Scopus subject areas

離散数学と組合せ数学
応用数学

文献へのアクセス

10.1016/S0166-218X(98)00048-1

他のファイルとリンク

引用スタイル

@article{dd22b616f54543db8e58ce976db28c8f,

title = "Pyramidal tours with step-backs and the asymmetric traveling salesman problem",

abstract = "In this paper, we introduce the notion of a pyramidal tour with step-backs which is an extension of a pyramidal tour. By using this idea we shall show that for a class of distance matrices an optimal tour of traveling salesman problem can be computed in polynomial time.",

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

author = "Hikoe Enomoto and Yoshiaki Oda and Katsuhiro Ota",

year = "1998",

month = oct,

day = "5",

doi = "10.1016/S0166-218X(98)00048-1",

language = "English",

volume = "87",

pages = "57--65",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

number = "1-3",

}

TY - JOUR

T1 - Pyramidal tours with step-backs and the asymmetric traveling salesman problem

AU - Enomoto, Hikoe

AU - Oda, Yoshiaki

AU - Ota, Katsuhiro

PY - 1998/10/5

Y1 - 1998/10/5

N2 - In this paper, we introduce the notion of a pyramidal tour with step-backs which is an extension of a pyramidal tour. By using this idea we shall show that for a class of distance matrices an optimal tour of traveling salesman problem can be computed in polynomial time.

AB - In this paper, we introduce the notion of a pyramidal tour with step-backs which is an extension of a pyramidal tour. By using this idea we shall show that for a class of distance matrices an optimal tour of traveling salesman problem can be computed in polynomial time.

KW - A pyramidal tour

KW - Polynomially solvable classes

KW - The traveling salesman problem

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

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

U2 - 10.1016/S0166-218X(98)00048-1

DO - 10.1016/S0166-218X(98)00048-1

M3 - Article

AN - SCOPUS:0007628656

SN - 0166-218X

VL - 87

SP - 57

EP - 65

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 1-3

ER -

Pyramidal tours with step-backs and the asymmetric traveling salesman problem

抄録

ASJC Scopus subject areas

文献へのアクセス

他のファイルとリンク

フィンガープリント

引用スタイル