Three easy special cases of the euclidean travelling salesman problem
V. G. Deĭneko; J. A. Van der Veen; R. Rudolf; G. J. Woeginger
RAIRO - Operations Research - Recherche Opérationnelle (1997)
- Volume: 31, Issue: 4, page 343-362
- ISSN: 0399-0559
Access Full Article
top
How to cite
topDeĭneko, V. G., et al. "Three easy special cases of the euclidean travelling salesman problem." RAIRO - Operations Research - Recherche Opérationnelle 31.4 (1997): 343-362. <http://eudml.org/doc/105155>.
@article{Deĭneko1997,
author = {Deĭneko, V. G., Van der Veen, J. A., Rudolf, R., Woeginger, G. J.},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {distance matrix; travelling salesman problem; Demidenko conditions; Kalmanson conditions; Supnick conditions; polynomial time recognition algorithms},
language = {eng},
number = {4},
pages = {343-362},
publisher = {EDP-Sciences},
title = {Three easy special cases of the euclidean travelling salesman problem},
url = {http://eudml.org/doc/105155},
volume = {31},
year = {1997},
}
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
PB - EDP-Sciences
VL - 31
IS - 4
SP - 343
EP - 362
LA - eng
KW - distance matrix; travelling salesman problem; Demidenko conditions; Kalmanson conditions; Supnick conditions; polynomial time recognition algorithms
UR - http://eudml.org/doc/105155
ER -
References
top- 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. Zbl0367.68034MR433962
- 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. Zbl0858.68042
- 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). Zbl0366.90090MR456442
- 4. M. M. FLOOD, The traveling salesman problem, Operations Research, 1956, 4, pp. 61-75. MR78639
- 5. P. C. GILMORE, E. L. LAWLER and D. B. SHMOYS, Well-solved special cases, Chapter 4 in [8], pp. 87-143. Zbl0631.90081MR811471
- 6. C. H. PAPADIMITRIOU, The Euclidean travelling salesman problem is NP-complete, Theoretical Computer Science, 1977, 4, pp.237-244. Zbl0386.90057MR455550
- 7. K. KALMANSON, Edgeconvex circuits and the travelling salesman problem, Canadian Journal of Mathematics, 1975, 27, pp. 1000-1010. Zbl0284.05117MR396329
- 8. E. L. LAWLER, J. K. LENSTRA, A. H. G. RINNOOY KAN and D. B. SHMOYS, The travelling salesman problem, Wiley, Chichester, 1985. Zbl0562.00014MR811467
- 9. L. LOVÁSZ, Combinatorial Problems and Exercices, North-Holland, Amsterdam, 1978. Zbl0785.05001
- 10. F. P. PREPARATA and M. I. SHAMOS, Computational Geometry - an Introduction, Springer Verlag, New York, 1985. Zbl0759.68037MR805539
- 11. L. V. QUINTAS and F. SUPNICK, On some properties of shortest Hamiltonian circuits, American Mathematical Monthly, 1965, 72, pp. 977-980. Zbl0134.40603MR188872
- 12. F. SUPNICK, Extreme Hamiltonian lines, Annals of Math., 1957, 66, pp. 179-201. Zbl0078.16502MR88401
- 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. Zbl0813.90124MR1299086
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.