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:
Oct. 23, 2012
Filed:
May. 28, 2009
Applicants:
Reid Andersen, Seattle, WA (US);
Kumar Chellapilla, Sammamish, WA (US);
Chinmay Karande, Bellevue, WA (US);
Inventors:
Reid Andersen, Seattle, WA (US);
Kumar Chellapilla, Sammamish, WA (US);
Chinmay Karande, Bellevue, WA (US);
Assignee:
Microsoft Corporation, Redmond, WA (US);
Attorney:
Primary Examiner:
Assistant Examiner:
Int. Cl.
CPC ...
G06F 17/30 (2006.01);
U.S. Cl.
CPC ...
Abstract
Short paths are found with a small query time in scale-free directed graphs using a two-phase process by which data structures comprising shortest path trees are first pre-computed for a group of central vertices called 'hubs' that have short paths to most other vertices in the graph. In a query time phase, a short path between two vertices of interest in the graph is found by looking up the path to the root in each of the shortest path trees.