SEARCHING A VERTEX IN A PATH

摘要

Methods and systems for searching a path for a vertex include 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; determining whether the lower bounds cover all points in the path and, if so, determining that the vertex is not in the path; determining whether a number of uncovered points is below a path size threshold and, if so, performing a search of the uncovered points to determine whether the vertex is in the path; and if the number of uncovered points is above the path size threshold, repeating the steps of determining a lower bound, determining whether the lower bounds cover all points, and determining whether a number of points is below a path size threshold using the uncovered points as a new path.

主权项

1. A method for searching a path for a vertex, comprising:
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; determining whether the lower bounds cover all points in the path and, if so, determining that the vertex is not in the path; determining whether a number of uncovered points is below a path size threshold and, if so, performing a search of the uncovered points with a processor to determine whether the vertex is in the path; and if the number of uncovered points is above the path size threshold, repeating said steps of determining a lower bound, determining whether the lower bounds cover all points, and determining whether a number of points is below a path size threshold using the uncovered points as a new path.