Search

The well-known problem of weighted matching in an arbitrary graph H with n vertices is reduced to a matching problem for a bipartite graph with 2n vertices. The maximum matching of graph H with the minimum sum of weights of edges defined by matrix[c] is found in timeO ( n ) after ordering, in non-descending order, the values above the main diagonal. [ABSTRACT FROM AUTHOR]

The paper considers the minimization of the sum of weights of edges forming a subset U′ ⊂ U of the set of disjoint simple cycles at vertices υ ϵ V in graph H = (V,U) and covering V. The problem under study (2-f problem) is polynomially solvable in algorithms that are characterized by technical difficulties that hinder the acceleration of computing. The 2-f problem is solved by reducing it to a simpler bipartite case. The result is represented by a perfect matching of bipartite graph corresponding to the solution of the assignment problem, where each circuit of cyclic expansion contains at least three arcs. [ABSTRACT FROM AUTHOR]

The paper proposes a new method to solve the assignment problem based on recursive derivation of the optimal solution. The assignment problem is formulated in the rearrangement matrix form that allows the use of the matrix approach to optimal solution. The algorithm is to find the minimum total weight matching in the bipartite graph with 2n vertices. The computational scheme of the recurrence method for solving the assignment problem is presented in the form adapted for implementation on a computer. [ABSTRACT FROM AUTHOR]

A class of polynomially solvable problems of combinatorial optimization is illustrated by the example of the traveling salesman problem. It is proved that this class includes problems for which the structure of initial data is specially modeled. [ABSTRACT FROM AUTHOR]