Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


miami1228887237.pdf (3.43 MB)

ETD Abstract Container

Abstract Header

Computing point-to-point shortest path using an approximate distance oracle

Poudel, Pawan
http://rave.ohiolink.edu/etdc/view?acc_num=miami1228887237

Abstract Details

2008, Master of Computer Science, Miami University, Computer Science and Systems Analysis.
We propose an extremely simple and efficient shortest path algorithm that computes an optimal shortest path between a pair of points in a metric space. Our algorithm works similarly to Dijkstra’s algorithm, but uses heuristic information provided by an approximate distance oracle to prune nodes that cannot be on the shortest path. Our algorithm returns the exact shortest path in time (CS*)O(dim) using this linear size data structure, where S* is the number of vertices in the shortest path, dim is the doubling dimension of input graph, and C is a constant. We prove that this is nearly optimal by proving a lower-bound of (CS*)Ω(dim). This paper presents theoretical and experimental results to prove that if there exist efficient distance oracles for road maps, then our algorithm explores very few nodes compared to Dijkstra’s algorithm, A* algorithm, and Goldberg, et al’s ALT algorithms.
William Brinkman, Dr. (Advisor)
James Kiper, Dr. (Committee Member)
Lukasz Opyrchal, Dr. (Committee Member)
43 p.
Computer Science
APPROXIMATE DISTANCE ORACLE; SHORTEST PATH; vertices

Recommended Citations

Citations

  • Poudel, P. (2008). Computing point-to-point shortest path using an approximate distance oracle [Master's thesis, Miami University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=miami1228887237

    APA Style (7th edition)

  • Poudel, Pawan. Computing point-to-point shortest path using an approximate distance oracle. 2008. Miami University, Master's thesis. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=miami1228887237.

    MLA Style (8th edition)

  • Poudel, Pawan. "Computing point-to-point shortest path using an approximate distance oracle." Master's thesis, Miami University, 2008. http://rave.ohiolink.edu/etdc/view?acc_num=miami1228887237

    Chicago Manual of Style (17th edition)

miami1228887237
2,590
© 2008, all rights reserved.
This open access ETD is published by Miami University and OhioLINK.