Finding extremal carcasses with preset vertex degrees by the replacement method (Q1377956)

The class of trees (carcasses) on graphs is finding expanding applications in engineering and technical computer science, computer-aided design, automatic formation of dimensional chains, analysis and synthesis of technological processes, etc. There are known classic algorithms for finding minimal carcasses on nonoriented graphs, such as the Prim, Dijkstra, Kraskal, and other algorithms. However, new application problems have required reformulating model problems concerning carcasses on graphs as well as creating methods and algorithms for solving them. \textit{N. Christofides} [Graph theory. An algorithmic approach (1975; Zbl 0321.94011)] formulated the general problem ``on basic subgraphs with preset vertex degrees'': \[ \sum^n_{i=1} \sum^n_{j=1} c_{ij} x_{ij}\to\min,\tag{1} \] where \(x\in\{0, 1\}\), and \(c_{ij}\) is the weight of the edge connecting the vertices \(i\) and \(j\). The introduction of preset vertex degrees was formalized in [\textit{A. F. Gorshkov} and \textit{Yu. M. Solomentsev}, Dokl. Akad. Nauk, Ross. Akad. Nauk 337, No. 2, 151-153 (1994) (Russian), and Russ. Acad. Sci., Dokl., Math. 50, No. 1, 23-27 (1995; Zbl 0842.05084) (English)] with the vector \[ S= (\sigma_1,\sigma_2,\dots, \sigma_i,\dots,\sigma_n)\tag{2} \] of fixed degrees. Problem (1), (2) will be called the Christofides problem. A particular solution to this problem for a one-component carcass with a preset degree of a single vertex was obtained with the Gabow algorithm [see \textit{H. N. Gabow}, Networks 8, 201-208 (1978; Zbl 0384.90105)]. The Gabow algorithm however does not give a complete solution to the Christofides problem when the degrees of all vertices are preset. For the first time, the Christofides problem was solved by the replacement method [see \textit{A. F. Gorshkov}, Sib. Mat. Zh. 26, No. 1(149), 44-48 (1985; Zbl 0571.05029)]. We consider minimization problems and problems on nonoriented graphs. However, the replacement method, which is completely reversible, can also be applied to solve maximization problems and problems on oriented graphs.