Kalmanson combinatorial conditions
In mathematics, the Kalmanson combinatorial conditions are a set of conditions on the distance matrix used in determining the solvability of the traveling salesman problem. These conditions apply to a special kind of cost matrix, the Kalmanson matrix, and are named after Kenneth Kalmanson.
References
- Kalmanson, Kenneth (1975), "Edgeconvex circuits and the traveling salesman problem", Canadian Journal of Mathematics 27 (5): 1000–1010, doi:10.4153/CJM-1975-104-6, MR 0396329.
- Klinz, Bettina; Woeginger, Gerhard J. (1999), "The Steiner tree problem in Kalmanson matrices and in circulant matrices", Journal of Combinatorial Optimization 3 (1): 51–58, doi:10.1023/A:1009881510868, MR 1702465.
- Deĭneko, V. G.; van der Veen, J. A.; Rudolf, R.; Woeginger, G. J. (1997), "Three easy special cases of the Euclidean travelling salesman problem", RAIRO Recherche Opérationnelle 31 (4): 343–362, MR 1491043.
- Okamoto, Yoshio (2004), "Traveling salesman games with the Monge property", Discrete Applied Mathematics 138 (3): 349–369, doi:10.1016/j.dam.2003.08.005, MR 2049654.
- Çela, Eranda (1998), The Quadratic Assignment Problem: Theory and Algorithms, Combinatorial Optimization 1, Dordrecht: Kluwer Academic Publishers, ISBN 0-7923-4878-8, MR 1490831.
This article is issued from Wikipedia - version of the Saturday, September 19, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.