Institutional Scholarship

Contraction Hierarchies

Show simple item record

dc.contributor.advisor Lindell, Steven Griffin, Ashley 2014-07-15T18:39:30Z 2014-07-15T18:39:30Z 2014
dc.description.abstract Optimization of route planning is essential to everyday tasks such as planning trips and traffic simulation. In order to optimize routes in large graphs such as transportation networks, an algorithm must be able to quickly find the shortest path from some source to a specified destination. The contraction hierarchy algorithm is a proposed solution to optimization of route planning. This algorithm has two stages: the first stage consists of ordering the nodes by some importance and removing nodes according to their importance to create a graph in which the shortest paths between nodes are preserved. The second stage is the query in which a shortest path is calculated using a bidirectional Dijkstra search.
dc.description.sponsorship Haverford College. Department of Computer Science
dc.language.iso eng
dc.subject.lcsh Contraction operators
dc.title Contraction Hierarchies
dc.type Thesis
dc.rights.access Haverford users only

Files in this item

This item appears in the following Collection(s)

Show simple item record Except where otherwise noted, this item's license is described as



My Account