|
Chelyabinskiy Fiziko-Matematicheskiy Zhurnal, 2016, Volume 1, Issue 1, Pages 16–23
(Mi chfmj2)
|
|
|
|
Mathematics
On optimal marking algorithms
M. N. Alekseeva, F. M. Alekseevb 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.
Received: 18.02.2015 Revised: 02.02.2016
Citation:
M. N. Alekseev, F. M. Alekseev, “On optimal marking algorithms”, Chelyab. Fiz.-Mat. Zh., 1:1 (2016), 16–23
Linking options:
https://www.mathnet.ru/eng/chfmj2 https://www.mathnet.ru/eng/chfmj/v1/i1/p16
|
Statistics & downloads: |
Abstract page: | 134 | Full-text PDF : | 52 | References: | 21 |
|