DYNAMIC-PROGRAMMING AND THE GRAPHICAL TRAVELING SALESMAN PROBLEM

被引：9

作者：

FONLUPT, J ^{[1
]}

NACHEF, A ^{[1
]}

机构：

[1] UCO,INST MATH,F-49005 ANGERS,FRANCE

来源：

JOURNAL OF THE ACM | 1993年 / 40卷 / 05期

关键词：

ALGORITHMS; THEORY; ALGORITHM; COMBINATORIAL OPTIMIZATION; DYNAMIC PROGRAMMING; GRAPH; TRAVELING SALESMAN PROBLEM;

D O I：

10.1145/174147.169803

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

In this paper, we study cases of polynomial resolution of the Traveling Salesman problem. First, we define a generalization of the Traveling Salesman problem where the cost of an edge depends on the number of times this edge is visited in a tour; here, an edge may be visited 0, 1, or 2 times. By this generalization, we can find polynomial algorithms to solve the Traveling Salesman problem on certain classes of graphs that are built from basic graphs by operations called r-sum, with r fixed. The underlying ideas of these algorithms are similar to dynamic programming techniques. Our classes contain most of the known instances for which the graphical and classical salesman problems are polynomial.

引用

页码：1165 / 1187

页数：23

共 12 条

[1]

Aho A., 1983, DATA STRUCTURES ALGO

[2]

BARAHONA G, 1985, 77 MATH I U AUGSB PR

[3] HALIN GRAPHS AND THE TRAVELING SALESMAN PROBLEM [J].

CORNUEJOLS, G ;

NADDEF, D ;

PULLEYBLANK, WR .

MATHEMATICAL PROGRAMMING, 1983, 26 (03) :287-294

[4]

Dirac, 1963, CANAD MATH B, V6, P183

[5]

FLEISCHMANN B, 1983, CUTTING PLANE PROCED

[6]

FONLUPT J, 1987, ARTEMISRT23 I MATH A

[7]

FONLUPT J, 1985, IN PRESS MATH PROG

[8]

Hopcroft J. E., 1973, SIAM Journal on Computing, V2, P135, DOI 10.1137/0202012

[9]

NACHEF A, 1988, THESIS U GRENOBLE GR

[10] ORDER-PICKING IN A RECTANGULAR WAREHOUSE - A SOLVABLE CASE OF THE TRAVELING SALESMAN PROBLEM [J].

RATLIFF, HD ;

ROSENTHAL, AS .

OPERATIONS RESEARCH, 1983, 31 (03) :507-521

← 1 2 →