The Maximum Graph Cut Problem



The Max Cut problem is a classified NP-hard optimization problem. It can be defined as:

-Undirected and unweighted graph G=(V,E).

-A partition of V into disjoint sets {V1,V2}




Given a graph G, find the partition of his vertexs in two groups {V1,V2} that maximizes the cardinality of the cut, i.e., the number of edges with one end point in V1 and one endpoint in V2.


Problem Instances

In order to define an instance of this problem we need to provide all the information about the Graph. This means: his Vertex Set and the associated Edge Set between pairs of vertexs. The edges are unweighted.


Related Bibliography and Papers

Computers and Intractability: A Guide to the Theory of Np-Completeness
by Michael R. Garey, David S. Johnson
How to Solve It: Modern Heuristics
by Zbigniew Michalewicz, David B. Fogel
A compendium of NP optimization problems

Last Updated: 5/06/03                                                                                                                  For any question or suggestion, click here to contact with us.