Determining optimum graph bisection using a tree and pruning the tree using a packing lower bound
US8886573B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Apr 4, 2012 |
| Grant date | Nov 11, 2014 |
| Priority date | — |
| Expiry date | Jan 15, 2033 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/9024
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
Techniques are described for graph partitioning, and in particular, graph bisection. A lower bound is provided that is computed in near-linear time. These bounds may be used to determine optimum solutions to real-world graphs with many vertices (e.g., more than a million for road networks, or tens of thousands for VLSI and mesh instances). A packing lower bound technique determines lower bounds in a branch-and-bound tree, reducing the number of tree nodes. Techniques are employed to assign vertices without branching on them, again reducing the size of the tree. Decomposition is provided to translate an input graph into less complex subproblems. The decomposition boosts performance and determines the optimum solution to an input by solving subproblems independently. The subproblems can be solved independently using a branch-and-bound approach to determine the optimum bisection.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.