Graph Partitioning Task

See: Graph Partition, Graph Segmentation, Graph Partitioning Algorithm, Normalized Cuts Algorithm.

References

http://en.wikipedia.org/wiki/Graph_partition
- In mathematics, the graph partitioning problem consists of dividing a graph into pieces, such that the pieces are of about the same size and there are few connections between the pieces. Consider a graph G(V, E), where [math]\displaystyle{ V }[/math] denotes the set of vertices and $E$ the set of edges. The standard (unweighted) version of the graph partition problem is: Given [math]\displaystyle{ G }[/math] and an integer k > 1, partition [math]\displaystyle{ V }[/math] into [math]\displaystyle{ k }[/math] parts (subsets) V₁, V₂, ..., V_k such that the 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, and the balance criterion is [math]\displaystyle{ \max_i |V_i| \le (1+\varepsilon) \frac{|V|}{k}. }[/math] In the general (weighted) version, both vertices and edges can be weighted. The graph partitioning problem then consists of dividing [math]\displaystyle{ G }[/math] into [math]\displaystyle{ k }[/math] disjoint parts such that the parts have approximately equal weight and the size of the edge cuts is minimized. The size of a cut is the sum of the weights of the edges contained in it, while the weight of a part is the sum of the weights of the vertices in the part. When k = 2, the problem is also referred to as the graph bisection problem.