Volume 18, No 1, 2011, P. 27-40

UDC 519.1
A. V. Eremeev
On perfect colorings of line graphs

Abstract:
The computational complexity of optimal recombination for the traveling salesman problem is considered in the symmetric  and general cases. NP-hardness of these problems is proven and some approaches to their solution are indicated.
Ill. 3,  bibliogr. 15.

Keywords: traveling salesman problem, genetic algorithm, optimal recombination, computational complexity, problem transformation.

Eremeev Anton Valentinovich ¹
1. Omsk Branch of Sobolev Institute of Mathematics SB RAS,
13 Pevtsov str., 644099 Omsk, Russia
e-mail: eremeev@ofim.oscsbras.ru