Patent · US Active

Enhanced reach-based graph processing using shortcuts

US7774734B2 · kind B2 · utility

5Cited by

16References

20Claims

0Family size

Assignee

Microsoft Corporation · US

Inventors

Andrew V. Goldberg · Redwood City, US
Renato F. Werneck · San Francisco, US
Haim Kaplan · Hod HaSharon, IL

Key dates

Filing date	Nov 6, 2006
Grant date	Aug 10, 2010
Priority date	—
Expiry date	Oct 4, 2027

Classification

Technology area (CPC G)Physics
CPC primaryG01C21/3446
WIPO fieldMeasurement
WIPO sectorInstruments

Abstract

An algorithm referred to as REAL for the point-to-point shortest path problem combines A* search with landmark-based lower bounds and reach-based pruning. A symbiosis of these techniques is described, which gives a range of time and space tradeoffs, including those that improve both of these complexity measures. Locality is improved and exact reach computation is described.

Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.