Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/43865
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)

Files in This Item:
File Description SizeFormat 
SCE10-0217.pdf
  Restricted Access
1.75 MBAdobe PDFView/Open

Google ScholarTM

Check

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.