A Linear Iterative Approach for Hierarchical Shortest Path Finding
| dc.contributor.author | Filho, Gutemberg Guerra | en_US |
| dc.contributor.author | Samet, Hanan | en_US |
| dc.date.accessioned | 2004-05-31T23:23:02Z | |
| dc.date.available | 2004-05-31T23:23:02Z | |
| dc.date.created | 2002-10 | en_US |
| dc.date.issued | 2002-11-08 | en_US |
| dc.description.abstract | We present a hierarchical approach that subdivides a network with $n$ vertices into $r$ regions with the same number $m$ of vertices ($n = r m$) and creates higher levels merging a constant number $c$ of adjacent regions. We propose linear iterative algorithms to find a shortest path and to expand this path into the lowest level. Since our approach is non-recursive, the complexity constants are small and the algorithms are more efficient in practice than other recursive optimal approaches. A hybrid shortest path algorithm to perform intra-regional queries in the lowest level is introduced. This strategy uses a subsequence of vertices that belong to the shortest path while actually computing the whole shortest path. The hybrid algorithm requires $O(m)$ time and space assuming an uniform distribution of vertices. This represents a further improvement concerning space, since a path view approach requires $O(m^{1.5})$ space in the lowest level. For higher $k$-levels, a path view approach spends $O(1)$ time and requires $O(c^k m)$ space. (UMIACS-TR-2002-97) | en_US |
| dc.format.extent | 1745954 bytes | |
| dc.format.mimetype | application/postscript | |
| dc.identifier.uri | http://hdl.handle.net/1903/1241 | |
| dc.language.iso | en_US | |
| dc.relation.isAvailableAt | Digital Repository at the University of Maryland | en_US |
| dc.relation.isAvailableAt | University of Maryland (College Park, Md.) | en_US |
| dc.relation.isAvailableAt | Tech Reports in Computer Science and Engineering | en_US |
| dc.relation.isAvailableAt | UMIACS Technical Reports | en_US |
| dc.relation.ispartofseries | UM Computer Science Department; CS-TR-4417 | en_US |
| dc.relation.ispartofseries | UMIACS; UMIACS-TR-2002-97 | en_US |
| dc.title | A Linear Iterative Approach for Hierarchical Shortest Path Finding | en_US |
| dc.type | Technical Report | en_US |
Files
Original bundle
1 - 1 of 1