The Minimum Graph Bisection Problem



The Bisection 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} with the same size.




A bisection of a graph G=(V,E) with an even number of vertices is a pair of disjoint subsets V1,V2 V of equal size. The cost of a bisection is the number of edges c=(a,b) E such that a V1 and b V2. The problem of Graph Bisection takes as input a graph with an even number of vertices and returns a bisection of minimum cost.

This problem arises frequently in real world applications, such as parallel scientific computing, VLSI design, or task scheduling.


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
TextBook Graph Bisection
by Andras Ferencz, Robert Szewczyk, Jonathan Weinstein, Jon Wilkening
A compendium of NP optimization problems

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