Institutional Scholarship

Contraction Hierarchies

Show simple item record

dc.contributor.advisor Lindell, Steven
dc.contributor.author Griffin, Ashley
dc.date.accessioned 2014-07-15T18:39:30Z
dc.date.available 2014-07-15T18:39:30Z
dc.date.issued 2014
dc.identifier.uri http://hdl.handle.net/10066/14331
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. en_US
dc.description.sponsorship Haverford College. Department of Computer Science. en_US
dc.language.iso en en_US
dc.rights.uri http://creativecommons.org/licenses/by-nc/3.0/us/
dc.subject.lcsh Contraction operators
dc.title Contraction Hierarchies en_US
dc.type Thesis (B.S.) en_US
dc.rights.access Haverford users only


Files in this item

This item appears in the following Collection(s)

Show simple item record

http://creativecommons.org/licenses/by-nc/3.0/us/ Except where otherwise noted, this item's license is described as http://creativecommons.org/licenses/by-nc/3.0/us/

Search


Browse

My Account