Настоящий доклад посвящен исследованию сложности классического алгоритма Литта, Мурти, Суини и Кэрол решения задачи коммивояжера и модификации этого алгоритма для решения задачи нескольких коммивояжеров. В модифицированном алгоритме используются аналогичные правила для оценки нижней границы целой функции и выбора ребра для ветвления. В отличие от алгоритма Литта и др. ветвления исходной задачи производится на q+1 новую задачу, где максимальное q - число подграфов, определяемое условием. В качестве меры сложности алгоритмов используются число арифметических операций T и объем памяти V, необходимые для решения задачи.
