The Maximum Graph Cut Problem


Description:The Max Cut problem is a classified NPhard optimization problem. It can be defined as: Input: Output: 

QuestionGiven 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 InstancesIn 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


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