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.
展开▼
