The max cut problem consists in finding a cut of maximum cardinality. The problem is NP-problem.
Then the max cut problem may be formulated as the following non linear integer program.
| Given a graph
G (N, E) a cut is defined by assigning a proper subset
S Ì N and taking all edges
between S and the complement of S. The max cut problem consists in finding a cut of maximum cardinality. The problem is NP-problem. Then the max cut problem may be formulated as the following non linear integer program. |
|
