Volume 18, No 1, 2011, P. 27-40
A. V. Eremeev
On perfect colorings of line graphs
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
1. Omsk Branch of Sobolev Institute of Mathematics SB RAS,
13 Pevtsov str., 644099 Omsk, Russia