Fast Algorithm to Find 2-Factor of Minimum Weight
- PDF / 199,323 Bytes
- 8 Pages / 594 x 792 pts Page_size
- 30 Downloads / 213 Views
FAST ALGORITHM TO FIND 2-FACTOR OF MINIMUM WEIGHT O. B. Matsiy,1 A. V. Morozov,2† and A. V. Panishev2‡
UDC 519.161
Abstract. 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 u Î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. Keywords: 2-factor, assignment problem, matching, bipartite graph, augmenting path. INTRODUCTION A subset U ¢ Ì U of edges of graph H = (V , U ) is called 2-factor if each node u ÎV is incident exactly to two edges. Subset M Ì U of edges of graph H = (V , U ) is called matching (perfect matching) if each node u ÎV is incident to no more than (exactly) one edge. The problem of finding the 2-factor of minimum weight (problem 2- f ) can be formulated as follows. Given a graph H = (V , U ) , where V is the set of nodes, | V | = n , and U is the set of edges, where each edge { i, j } has the weight cij Î R 0+ , and R 0+ is the set of nonnegative real numbers. In graph H , find the 2-factor with the minimum sum of weights of edges. The problem posed for complete graph H n always has a solution. The study [1] outlines the algorithm that finds, in a n-node complete graph, the 2-factor of minimum weight in time O ( n 3 ) . As is known from [2], for a spanning subgraph H of complete graph H n problem 2- f can be solved by reducing it to the problem of finding a matching of minimum weight in a graph with a significantly larger number of nodes and edges than in H . Matching is found in time O ( n 4 ) by the Edmonds algorithm or by its modifications, which include the procedure of finding a flower, i.e., cycle with 2k + 1 nodes, in which k edges form a matching, and flower cutting procedure, i.e., its replacement with one node [3]. Since a connected 2-factor is a Hamilton cycle of graph H n , the solution of the problem posed is used in the development of efficient algorithms with guaranteed estimates for problems of the class of traveling salesman problem, with a wide range of applications [3]. The majority of these algorithms is characterized by the same labor input assessment as the Edmonds algorithm. The possibility of finding the 2-factor of minimum weight in a polynomial time is the basis to choose the formulated problem as a relaxation, which provides lower estimates that are the closest to the optimum for today in exact algorithms of the solution of symmetric traveling salesman problem (STSP), constructed by the branch and bound algorithm [4, 5]. The main cause that hampers the evaluation of the lower bounds by the Edmonds algorithm in exact methods of STSP solution is the complexity of fl
Data Loading...
