Graph Partitioning Task

From GM-RKB
(Redirected from Graph Partitioning)
Jump to navigation Jump to search

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



References

2011

  • 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) V1, V2, ..., Vk 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.