Please use this identifier to cite or link to this item:
|Title:||Performance evaluation of contraction hierarchies in road networks||Authors:||Hardy, Jefry.||Keywords:||DRNTU::Engineering::Computer science and engineering::Theory of computation::Analysis of algorithms and problem complexity
DRNTU::Engineering::Computer science and engineering::Computer applications::Physical sciences and engineering
|Issue Date:||2011||Abstract:||Contraction hierarchy is the new idea of route planning technique. The theory is merely based on the concept of node contraction. At a time, one node is removed out of the graph and then the shortcuts are added to the corresponding remaining graph to reserve the shortest path distances. As the result, contraction hierarchy consists of the original graph plus the shortcuts. Having all the shortcuts added to the graph, a modified bidirectional Dijkstra algorithm is applied to acquire the shortest paths. This hierarchy has five times lower query time than the previous best hierarchical Dijkstra-based technique.||URI:||http://hdl.handle.net/10356/43865||Rights:||Nanyang Technological University||Fulltext Permission:||restricted||Fulltext Availability:||With Fulltext|
|Appears in Collections:||SCSE Student Reports (FYP/IA/PA/PI)|
Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.