Patent ID: 8738559

Claim:
A method for graph partitioning, comprising: receiving as input, at a computing device, a graph comprising a plurality of vertices and edges; filtering the graph using a plurality of natural cuts, the natural cuts being relatively sparse cuts bordering denser regions of the graph, each of the natural cuts computed by using a breadth-first search to find a minimum cut between a first set of vertices in a first region and a second set of vertices surrounding the first region, the minimum cut being a relatively sparse cut defining the first region as a denser region of the graph, the filtering comprising preserving in an un-contracted state edges of the graph that correspond to the natural cuts and contracting regions that do not correspond to the natural cuts to generate a filtered graph, by the computing device, wherein the filtered graph comprises a plurality of cells corresponding to the contracted regions, each cell comprising a different subset of the vertices; partitioning the graph by assembling the filtered graph to form a partitioned graph, the assembling comprising minimizing the number of edges between the cells using a greedy technique and a local search technique, by the computing device; and outputting the partitioned graph.