×

Searching a vertex in a path

  • US 9,483,514 B2
  • Filed: 03/16/2015
  • Issued: 11/01/2016
  • Est. Priority Date: 12/13/2012
  • Status: Expired due to Fees
First Claim
Patent Images

1. A method for searching a path for a vertex, comprising:

  • iteratively removing from consideration points in a path, until a number of remaining points is below a path size threshold, by;

    determining, for each of two endpoints in a path, a lower bound for a shortest path distance from each respective endpoint to a target vertex by calculating a relationship between known shortest path distances; and

    removing from consideration points closer to each respective endpoint than the respective lower bound to produce a shortened path; and

    searching the shortened path with a processor to determine whether the vertex is in the shortened path.

View all claims
  • 1 Assignment
Timeline View
Assignment View
    ×
    ×