Name
Abstract | ||
|---|---|---|
We present a heuristic search algorithm for the Rd Manhattan shortest path problem that achieves front-to-front bidirectionality in subquadratic time. In the study of bidirectional search algorithms, front-to-front heuris- tic computations were thought to be prohibitively expensive (at least quadratic time complexity); our algorithm runs in O(nlogd n )t ime and O(nlogd−1 n) space, where n is the number of visited vertices. We achieve this result by embedding the problem in Rd+1 and identifying heuristic calculations as instances of a dynamic closest-point problem, to which we then apply methods from computational geometry. |
Year | Venue | Keywords |
|---|---|---|
2003 | J. Graph Algorithms Appl. | heuristic search,shortest path,time complexity,computational geometry,search algorithm,shortest path problem |
Field | DocType | Volume |
Discrete mathematics,Combinatorics,Shortest path problem,Yen's algorithm,Bidirectional search,Shortest Path Faster Algorithm,Time complexity,Mathematics,Consistent heuristic,K shortest path routing,Euclidean shortest path | Journal | 7 |
Issue | Citations | PageRank |
3 | 0 | 0.34 |
References | Authors | |
8 | 1 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Po-Shen Loh | 1 | 133 | 18.68 |