Three easy special cases of the euclidean travelling salesman problem

Deĭneko, V. G.; Van der Veen, J. A.; Rudolf, R.; Woeginger, G. J.

Deĭneko, V. G. ; Van der Veen, J. A. ; Rudolf, R. ; Woeginger, G. J.

RAIRO - Operations Research - Recherche Opérationnelle, Tome 31 (1997) no. 4, pp. 343-362.

MR Zbl

@article{RO_1997__31_4_343_0,
     author = {De\u{i}neko, V. G. and Van der Veen, J. A. and Rudolf, R. and Woeginger, G. J.},
     title = {Three easy special cases of the euclidean travelling salesman problem},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {343--362},
     publisher = {EDP-Sciences},
     volume = {31},
     number = {4},
     year = {1997},
     mrnumber = {1491043},
     zbl = {0888.90141},
     language = {en},
     url = {http://www.numdam.org/item/RO_1997__31_4_343_0/}
}

TY  - JOUR
AU  - Deĭneko, V. G.
AU  - Van der Veen, J. A.
AU  - Rudolf, R.
AU  - Woeginger, G. J.
TI  - Three easy special cases of the euclidean travelling salesman problem
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 1997
SP  - 343
EP  - 362
VL  - 31
IS  - 4
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/RO_1997__31_4_343_0/
LA  - en
ID  - RO_1997__31_4_343_0
ER  -

%0 Journal Article
%A Deĭneko, V. G.
%A Van der Veen, J. A.
%A Rudolf, R.
%A Woeginger, G. J.
%T Three easy special cases of the euclidean travelling salesman problem
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 1997
%P 343-362
%V 31
%N 4
%I EDP-Sciences
%U http://www.numdam.org/item/RO_1997__31_4_343_0/
%G en
%F RO_1997__31_4_343_0

Deĭneko, V. G.; Van der Veen, J. A.; Rudolf, R.; Woeginger, G. J. Three easy special cases of the euclidean travelling salesman problem. RAIRO - Operations Research - Recherche Opérationnelle, Tome 31 (1997) no. 4, pp. 343-362. http://www.numdam.org/item/RO_1997__31_4_343_0/

Bibliographie
Cité par

1. K. S. Booth and G. S. Lueker, Testing for the consecutive ones property, interval graphs and graph planarity using PQ-tree algorithms, Journal of Computer and System Sciences, 1976, 13, pp.335-379. | MR | Zbl

2. V. G. Deĭneko, R. Rudolf and G. J. Woeginger, On the Recognition of Permuted Supnick and Incomplete Monge Matrices, SFB Report 05, Spezialforschungsbereich, "Optimierung und Kontrolle", TU Graz, Austria. | Zbl

V. M. Demidenko, A special case of travelling salesman problems, Izv.Akad. Nauk. BSSR, Ser.fiz.-mat nauk, 1976, 5, pp. 28-32 (in Russian). | MR | Zbl

4. M. M. Flood, The traveling salesman problem, Operations Research, 1956, 4, pp. 61-75. | MR

5. P. C. Gilmore, E. L. Lawler and D. B. Shmoys, Well-solved special cases, Chapter 4 in [8], pp. 87-143. | MR | Zbl

6. C. H. Papadimitriou, The Euclidean travelling salesman problem is NP-complete, Theoretical Computer Science, 1977, 4, pp.237-244. | MR | Zbl

7. K. Kalmanson, Edgeconvex circuits and the travelling salesman problem, Canadian Journal of Mathematics, 1975, 27, pp. 1000-1010. | MR | Zbl

8. E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan and D. B. Shmoys, The travelling salesman problem, Wiley, Chichester, 1985. | MR | Zbl

9. L. Lovász, Combinatorial Problems and Exercices, North-Holland, Amsterdam, 1978. | Zbl

10. F. P. Preparata and M. I. Shamos, Computational Geometry - an Introduction, Springer Verlag, New York, 1985. | MR | Zbl

11. L. V. Quintas and F. Supnick, On some properties of shortest Hamiltonian circuits, American Mathematical Monthly, 1965, 72, pp. 977-980. | MR | Zbl

12. F. Supnick, Extreme Hamiltonian lines, Annals of Math., 1957, 66, pp. 179-201. | MR | Zbl

13. J. A. Van Der Veen, A new class of pyramidally solvable symmetric traveling salesmas problems, SIAM J. Disc. Math., 1994, 7, pp. 585-592. | MR | Zbl