Cuts in Undirected Graphs. II
- PDF / 152,493 Bytes
- 8 Pages / 594 x 792 pts Page_size
- 92 Downloads / 219 Views
CUTS IN UNDIRECTED GRAPHS. I²* F. Sharifov1† and L. Hulianytskyi1‡
UDC 519.8
Abstract. To improve the value of the objective function, two algorithms for transforming the current base into a new one are proposed. It is shown that the maximum cut problem on an undirected graph can be reduced to finding the base of the extended polynomial, for which the value of the minimum cut that separates the source and the sink is maximum. The necessary and sufficient conditions for optimality of the solution of the maximum cut problem on undirected graphs in terms of flow theory are formulated. Keywords: graphs, cuts, convex function, special polyhedra, polymatroid. INTRODUCTION The present paper continues the study [1], where the model of the maximum cut problem contains variables for each vertex of the considered graph. The specificity of its constraints is noteworthy since the initial feasible solution can be determined by means of a greedy algorithm in time O ( m) . The solution thus determined is an extreme point [2] of the polyhedron of its constraints, i.e., the basis [3] of polymatroid x Î B ( j ) (see [1]). Taking into account the specificity of the objective function, it is possible to derermine a feasible solution where the objective function is almost maximum. To this end, it is necessary to find the optimal linear ordering of vertices (with regard for the topology of the graph), according to the order established in it, to assign to many variables their maximum feasible value. Such feasible solution of the problem can be found by the algorithm [4] in time O ( nm). To each feasible solution there corresponds a spanning bipartite subgraph (for brevity, we will sometimes write “bipartite subgraph”) of the given graph, and the inverse is also true. Since the maximum cut problem is NP-hard, determining the linear ordering of vertices that can help finding the optimal solution of the problem by a greedy algorithm involves great difficulties. Two algorithms are proposed, to transform the above-mentioned original feasible solution into another one in order to enhance the value of the function. In the first algorithm, in the beginning, subsets of vertices of each share of this bipartite subgraph are determined in a certain way. As a result of elimination and inclusion of these subsets into different shares, a new feasible solution is obtained. If the value of the objective function is improved, the process continues with respect to the current solution; otherwise, the algorithm stops. In the second algorithm, to find a new feasible solution, the algorithm of transformation of one of the two arbitrary bases into the other, proposed in [5], is used. In the paper, we will show that the maximum cut problem on the given graph is equivalent to the problem of finding the minimum cut separating a source and a sink in a network, constructed with respect to the considered basis of the expanded polymatroid. We will formulate the necessary and sufficient optimality conditions for the solution of the maximum cut problem on undirected
Data Loading...
