Geodesic
On optimal marking algorithms
Čelâbinskij fiziko-matematičeskij žurnal, Tome 1 (2016) no. 1, pp. 16-23 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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, Kruskal’s algorithm.
Mots-clés : Prim’s algorithm 
@article{CHFMJ_2016_1_1_a1,
     author = {M. N. Alekseev and F. M. Alekseev},
     title = {On optimal marking algorithms},
     journal = {\v{C}el\^abinskij fiziko-matemati\v{c}eskij \v{z}urnal},
     pages = {16--23},
     year = {2016},
     volume = {1},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/CHFMJ_2016_1_1_a1/}
}
TY  - JOUR
AU  - M. N. Alekseev
AU  - F. M. Alekseev
TI  - On optimal marking algorithms
JO  - Čelâbinskij fiziko-matematičeskij žurnal
PY  - 2016
SP  - 16
EP  - 23
VL  - 1
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/CHFMJ_2016_1_1_a1/
LA  - ru
ID  - CHFMJ_2016_1_1_a1
ER  - 
%0 Journal Article
%A M. N. Alekseev
%A F. M. Alekseev
%T On optimal marking algorithms
%J Čelâbinskij fiziko-matematičeskij žurnal
%D 2016
%P 16-23
%V 1
%N 1
%U http://geodesic.mathdoc.fr/item/CHFMJ_2016_1_1_a1/
%G ru
%F CHFMJ_2016_1_1_a1
M. N. Alekseev; F. M. Alekseev. On optimal marking algorithms. Čelâbinskij fiziko-matematičeskij žurnal, Tome 1 (2016) no. 1, pp. 16-23. http://geodesic.mathdoc.fr/item/CHFMJ_2016_1_1_a1/

[1] T. H. Cormen et al., Introduction to Algorithms, 2nd Edition, MIT Press and McGraw – Hill, 2001 | MR | Zbl

[2] N. Kristofides, Graph theory: algorithmic approach, Mir Publ., Moscow, 1978, 432 pp. (In Russ.) | MR