Geodesic
An approximate algorithm for finding a maximum-weight $d$-homogeneous connected spanning subgraph in a~complete graph with random edge weights
Diskretnyj analiz i issledovanie operacij, Tome 13 (2006) no. 2, pp. 3-20.

Voir la notice de l'article provenant de la source Math-Net.Ru

An approximation algorithm is suggested for the problem of finding a $d$-regular spanning connected subgraph of maximum weight in a complete undirected weighted $n$-vertex graph. Probabilistic analysis of the algorithm is carried out for the problem with random input data (some weights of edges) in the case of a uniform distribution of the weights of edges and in the case of a minorized type distribution. It is shown that the algorithm finds an asymptotically optimal solution with time complexity $O(n^2)$ when $d=o(n)$. For the minimization version of the problem, an additional restriction on the dispersion of weights of the graph edges is added to the condition of the asymptotical optimality of the modified algorithm. 
@article{DA_2006_13_2_a0,
     author = {A. E. Baburin and E. Kh. Gimadi},
     title = {An approximate algorithm for finding a maximum-weight $d$-homogeneous connected spanning subgraph in a~complete graph with random edge weights},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {3--20},
     publisher = {mathdoc},
     volume = {13},
     number = {2},
     year = {2006},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2006_13_2_a0/}
}
TY  - JOUR
AU  - A. E. Baburin
AU  - E. Kh. Gimadi
TI  - An approximate algorithm for finding a maximum-weight $d$-homogeneous connected spanning subgraph in a~complete graph with random edge weights
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2006
SP  - 3
EP  - 20
VL  - 13
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2006_13_2_a0/
LA  - ru
ID  - DA_2006_13_2_a0
ER  - 
%0 Journal Article
%A A. E. Baburin
%A E. Kh. Gimadi
%T An approximate algorithm for finding a maximum-weight $d$-homogeneous connected spanning subgraph in a~complete graph with random edge weights
%J Diskretnyj analiz i issledovanie operacij
%D 2006
%P 3-20
%V 13
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2006_13_2_a0/
%G ru
%F DA_2006_13_2_a0
A. E. Baburin; E. Kh. Gimadi. An approximate algorithm for finding a maximum-weight $d$-homogeneous connected spanning subgraph in a~complete graph with random edge weights. Diskretnyj analiz i issledovanie operacij, Tome 13 (2006) no. 2, pp. 3-20. http://geodesic.mathdoc.fr/item/DA_2006_13_2_a0/

[1] Baburin A. E., Gimadi E. Kh., “Ob odnom obobschenii zadachi kommivoyazhëra na maksimum”, Diskret. analiz i issled. operatsii. Ser. 1, 13:3 (2006), 3–12 | MR

[2] Gimadi E. Kh., Glebov N. I., Perepelitsa V. A., “Algoritmy s otsenkami dlya zadach diskretnoi optimizatsii”, Problemy kibernetiki, 31, Nauka, M., 1975, 35–42

[3] Petrov V. V., Predelnye teoremy dlya summ nezavisimykh sluchainykh velichin, Nauka, M., 1987 | MR

[4] Baburin E., Gimadi E. Kh., “Approximation algorithms for finding a maximum-weight spanning connected subgraph with given vertex degrees”, Operations Research Proceedings 2004 \bookunfo Selected Papers. International Conference OR 2004, Tilburg, Springer, Berlin, 2005, 343–351

[5] Gimadi E. Kh., Serdukov A. I., “A problem of finding the maximal spanning connected subgraph with given vertex degrees”, Operations Research Proceedings 2004, Selected Papers. International Conference OR 2000, Heidelberg, Springer, Berlin, 2001, 55–59 | MR | Zbl

[6] The traveling salesman problem and its variations, Kluwer Academic Publishers, Dordrecht–Boston–London, 2003