Graph bisection
 | This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these messages)
No issues specified. Please specify issues, or remove this template. |
The graph bisection problem in mathematics consists of dividing a graph into two pieces, such that the pieces are of about the same size and there are few connections between the pieces.
Consider a graph , where V denotes the set of vertices and E the set of edges. The standard (unweighted) version of the graph bisection problem is: Given G, partition V into two parts (subsets) V1, V2 such that the two parts are disjoint and have equal size, and the number of edges with endpoints in different parts is minimized. In practical applications, a small imbalance in the part sizes is usually allowed.
The graph bisection problem correspond to the graph partitioning problem when the number of partitions is equal to two.