37 Scopus citations


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 50 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 electrical power distribution networks, a slow-coherency-based islanding strategy is used as a prevention against the cascading failures. In this paper, we concentrate on the graph partition problems which are encountered in electric power distribution networks. In this environment, two different definitions of capacity of a cut are used. In the first definition, capacity of a cut is taken to be the difference of the edge weights going from V1 to V 2 and from V2 to V1. In the second definition, the capacity of a cut is taken to be the maximum of sum of the edge weights going from V1 to V2 and from V2 to V 1. 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 definitions of the capacity of a cut, the minimum cut computation problem becomes NP-complete. We provide an optimal solution to the problems using mathematical programming techniques. In addition, we also provide heuristic solutions and compare the performance with that of the optimal solution.

Original languageEnglish (US)
Pages (from-to)778-797
Number of pages20
JournalEuropean Transactions on Electrical Power
Issue number6
StatePublished - Sep 2009


  • Computational complexity
  • Electrical power network
  • Graph partitioning
  • Heuristic algorithm
  • Integer linear programming
  • Islanding

ASJC Scopus subject areas

  • Energy Engineering and Power Technology
  • Electrical and Electronic Engineering


Dive into the research topics of 'A new min-cut problem with application to electric power network partitioning'. Together they form a unique fingerprint.

Cite this