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:
Jan. 29, 2013
Filed:
Jan. 10, 2011
Daniel Delling, Mountain View, CA (US);
Andrew V. Goldberg, Redwood City, CA (US);
Andreas Nowatzyk, San Jose, CA (US);
Renato F. Werneck, San Francisco, CA (US);
Daniel Delling, Mountain View, CA (US);
Andrew V. Goldberg, Redwood City, CA (US);
Andreas Nowatzyk, San Jose, CA (US);
Renato F. Werneck, San Francisco, CA (US);
Microsoft Corporation, Redmond, WA (US);
Abstract
The non-negative single-source shortest path (NSSP) problem is solved on a graph by using a preprocessing phase and then, in a query phase, computing the distances from a given source in the graph with a linear sweep over all the vertices. Contraction hierarchies may be used in the preprocessing phase and in the query phase. Optimizations may include reordering the vertices in advance to exploit locality, performing multiple NSSP computations simultaneously, marking vertices during initialization, and using parallelism. Techniques may be performed on a graphics processing unit (GPU). This makes applications based on all-pairs shortest-paths practical for continental-sized road networks. The applications include, for example, computing graph diameter, exact arc flags, and centrality measures such as exact reaches or betweenness.