TY - GEN
T1 - A new min-cut problem with application to electric power network partitioning
AU - Sen, Arunabha
AU - Ghosh, Pavel
AU - Vittal, Vijay
AU - Yang, Bo
PY - 2006
Y1 - 2006
N2 - The problem of partitioning a graph into two or more subgraphs that satisfies certain conditions is encountered in many different domains. Accordingly, graph partitioning problem has been studied extensively in the last fifty years. The most celebrated result among this class of problems is the max flow = min cut theorem due to Ford and Fulkerson. Utilizing the modifications suggested by Edmonds and Karp, it is well known that the minimum capacity cut in the directed graph with edge weights can be computed in polynomial time. If the partition divides the node set V into subsets V1 and V2, where V1 contains one of the specified nodes s and V2 contains the other specified node t, the capacity of a cut is defined as the sum of the edge weights going from V1 to V2. In this paper, we consider a graph partition problem which is encountered in electric power distribution networks. In this environment, the capacity of a cut is defined as the absolute value of the difference of the edge weights going from V1 to V2 and V2 to V1. Surprisingly, with slight change of the definition of the capacity of a cut, the computational complexity of the problem changes significantly. In this paper we show that with the new definition of the capacity of a cut, the minimum cut computation problem becomes NP-complete. We provide an optimal solution to the problem using mathematical programming techniques. In addition, we also provide a heuristic solution and compare the performance of the optimal solution with the heuristic solution. We also consider a few other closely related problems.
AB - The problem of partitioning a graph into two or more subgraphs that satisfies certain conditions is encountered in many different domains. Accordingly, graph partitioning problem has been studied extensively in the last fifty years. The most celebrated result among this class of problems is the max flow = min cut theorem due to Ford and Fulkerson. Utilizing the modifications suggested by Edmonds and Karp, it is well known that the minimum capacity cut in the directed graph with edge weights can be computed in polynomial time. If the partition divides the node set V into subsets V1 and V2, where V1 contains one of the specified nodes s and V2 contains the other specified node t, the capacity of a cut is defined as the sum of the edge weights going from V1 to V2. In this paper, we consider a graph partition problem which is encountered in electric power distribution networks. In this environment, the capacity of a cut is defined as the absolute value of the difference of the edge weights going from V1 to V2 and V2 to V1. Surprisingly, with slight change of the definition of the capacity of a cut, the computational complexity of the problem changes significantly. In this paper we show that with the new definition of the capacity of a cut, the minimum cut computation problem becomes NP-complete. We provide an optimal solution to the problem using mathematical programming techniques. In addition, we also provide a heuristic solution and compare the performance of the optimal solution with the heuristic solution. We also consider a few other closely related problems.
UR - http://www.scopus.com/inward/record.url?scp=84940665077&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84940665077&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:84940665077
T3 - 44th Annual Allerton Conference on Communication, Control, and Computing 2006
SP - 589
EP - 598
BT - 44th Annual Allerton Conference on Communication, Control, and Computing 2006
PB - University of Illinois at Urbana-Champaign, Coordinated Science Laboratory and Department of Computer and Electrical Engineering
T2 - 44th Annual Allerton Conference on Communication, Control, and Computing 2006
Y2 - 27 September 2006 through 29 September 2006
ER -