M. N. Alekseev, F. M. Alekseev, “On optimal marking algorithms”, Chelyab. Fiz.-Mat. Zh., 2016, Volume 1, Issue 1,Pages <nobr>16

Mathematics

On optimal marking algorithms

M. N. Alekseev^a, F. M. Alekseev^b

^a Chelyabinsk State University, Chelyabinsk, Russia
^b Moscow Institute of Physics and Technology, Dolgoprudnyj, Russia

Abstract: The problem of choosing of the marking optimal order is considered as a special case of the traveling salesman problem. The algorithms for exact and approximate solutions search for the problem are proposed. The estimates of the algorithms complexity and possible approaches to their improvement are discussed.

Keywords: the traveling salesman problem, undirected weighted graph, minimum spanning tree, Hamiltonian path, dynamic programming, greedy algorithm, Prim’s algorithm, Kruskal’s algorithm.

UDC: 519.17

Received: 18.02.2015
Revised: 02.02.2016