×

GRAPH PARTITIONING WITH NATURAL CUTS

  • US 20120192138A1
  • Filed: 01/24/2011
  • Published: 07/26/2012
  • Est. Priority Date: 01/24/2011
  • Status: Active Grant
First Claim
Patent Images

1. A method for graph partitioning, comprising:

  • receiving as input, at a computing device, a graph comprising a plurality of vertices and arcs and a plurality of cells, each cell comprising a different subset of the vertices;

    filtering the graph using a plurality of natural cuts to contract a plurality of regions of the graph to generate a filtered graph, by the computing device;

    assembling a partitioned graph from the filtered graph using a greedy technique and a local search technique, by the computing device; and

    outputting the partitioned graph.

View all claims
  • 2 Assignments
Timeline View
Assignment View
    ×
    ×