Geodesic
Certain generalization of the maximum traveling salesman problem
Diskretnyj analiz i issledovanie operacij, Tome 13 (2006) no. 3, pp. 3-12.

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

The problem is considered of finding in a complete undirected weighted graph a connected spanning subgraph with the given degrees of the vertices having maximum total weight of the edges. An approximate polynomial algorithm is presented for this problem. The algorithm is analyzed, and some upper bounds of its error are established in the general case as well as in the metric and Euclidean cases. 
@article{DA_2006_13_3_a0,
     author = {A. E. Baburin and E. Kh. Gimadi},
     title = {Certain generalization of the maximum traveling salesman problem},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {3--12},
     publisher = {mathdoc},
     volume = {13},
     number = {3},
     year = {2006},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2006_13_3_a0/}
}
TY  - JOUR
AU  - A. E. Baburin
AU  - E. Kh. Gimadi
TI  - Certain generalization of the maximum traveling salesman problem
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2006
SP  - 3
EP  - 12
VL  - 13
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2006_13_3_a0/
LA  - ru
ID  - DA_2006_13_3_a0
ER  - 
%0 Journal Article
%A A. E. Baburin
%A E. Kh. Gimadi
%T Certain generalization of the maximum traveling salesman problem
%J Diskretnyj analiz i issledovanie operacij
%D 2006
%P 3-12
%V 13
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2006_13_3_a0/
%G ru
%F DA_2006_13_3_a0
A. E. Baburin; E. Kh. Gimadi. Certain generalization of the maximum traveling salesman problem. Diskretnyj analiz i issledovanie operacij, Tome 13 (2006) no. 3, pp. 3-12. http://geodesic.mathdoc.fr/item/DA_2006_13_3_a0/

[1] Kostochka A. V., Serdyukov A. I., “Polinomialnye algoritmy s otsenkami 3/4 i 5/6 dlya zadachi kommivoyazhera na maksimum”, Upravlyaemye sistemy, Sb. nauch. tr., no. 26, In-t matematiki SO AN SSSR, Novosibirsk, 1985, 55–59 | MR

[2] Serdyukov A. I., “Asimptoticheski tochnyi algoritm dlya zadachi kommivoyazhera na maksimum v evklidovom prostranstve”, Upravlyaemye sistemy, Sb. nauch. tr., no. 27, In-t matematiki SO AN SSSR, Novosibirsk, 1987, 79–87 | MR

[3] Kharari F., Teoriya grafov, Mir, M., 1973 | MR

[4] Edmonds J., Johnson E. L., “Matchings: a well solvable class of integer linear programs”, Combinatorial structures and their applications, Gordon and Breach, New York, 1970, 89–92 | MR

[5] Gabow H. N., “An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems”, Proc. 15th annual ACM symposium on theory of computing (Boston, April 25–27, 1983), ACM, New York, 1983, 448–456

[6] Gimadi E. Kh., Serdukov A. I., “A problem of finding the maximal spanning connected subgraph with given vertex degrees”, Operation Research Proceedings, 2000, Springer-Verlag, Berlin, 2001, 55–59 | MR | Zbl

[7] Havel V., “A note to question of existance of finite graphs”, Casopis Pest Mat., 80 (1955), 477–480 | MR | Zbl

[8] Lawler E. L., Lenstra J. K., Rinnoy Kan A. H. G., Shmoys D. B. (eds.), The traveling salesman problem: A guided tour of combinatorial optimization, John Wiley Sons, Chichester, 1985 | MR | Zbl

[9] A. Punnen and G. Gutin (eds.), The traveling salesman problem and its variations, Kluwer Academic Publishers, Dordrecht, Boston, London, 2003 | MR