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" (PDF), 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, vol. 1, Dordrecht: Kluwer Academic Publishers, ISBN 0-7923-4878-8, MR 1490831.