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

UDC 519.1
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
e-mail: eremeev@ofim.oscsbras.ru

 © Sobolev Institute of Mathematics, 2015