首页>
外国专利>
Determining optimum graph bisection using a tree and pruning the tree using a packing lower bound
Determining optimum graph bisection using a tree and pruning the tree using a packing lower bound
展开▼
机译:使用树确定最佳图二等分并使用填充下界修剪树
展开▼
页面导航
摘要
著录项
相似文献
摘要
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.
展开▼