Certain generalization of the maximum traveling salesman problem |
| |
| Authors: | A. E. Baburin E. Kh. Gimadi |
| |
| Affiliation: | (1) Sobolev Institute of Mathematics, pr. Akad. Koptyuga 4, Novosibirsk, 630090, Russia |
| |
| Abstract: | 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. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
