Geodesic
Three easy special cases of the euclidean travelling salesman problem
RAIRO - Operations Research - Recherche Opérationnelle, Tome 31 (1997) no. 4, pp. 343-362.

Voir la notice de l'article provenant de la source Numdam

@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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/item/RO_1997__31_4_343_0/

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. | Zbl | MR

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). | Zbl | MR

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. | Zbl | MR

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

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

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

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. | Zbl | MR

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

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

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. | Zbl | MR