The patent badge is an abbreviated version of the USPTO patent document. The patent badge does contain a link to the full patent document.
The patent badge is an abbreviated version of the USPTO patent document. The patent badge covers the following: Patent number, Date patent was issued, Date patent was filed, Title of the patent, Applicant, Inventor, Assignee, Attorney firm, Primary examiner, Assistant examiner, CPCs, and Abstract. The patent badge does contain a link to the full patent document (in Adobe Acrobat format, aka pdf). To download or print any patent click here.
Patent No.:
Date of Patent:
Nov. 11, 2014
Filed:
Apr. 04, 2012
Daniel Delling, Mountain View, CA (US);
Andrew V. Goldberg, Redwood City, CA (US);
Ilya Razenshteyn, Nizhniy Novgorod, RU;
Renato F. Werneck, San Francisco, CA (US);
Daniel Delling, Mountain View, CA (US);
Andrew V. Goldberg, Redwood City, CA (US);
Ilya Razenshteyn, Nizhniy Novgorod, RU;
Renato F. Werneck, San Francisco, CA (US);
Microsoft Corporation, Redmond, WA (US);
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.