===== AE 2010: 5. Vorlesung (18. Mai) =====
==== Kürzeste Wege Suche in Straßennetzwerken ===

  * Dijkstra's [[http://dx.doi.org/10.1007/BF01386390|Originalpaper von 1959]] zu seinem SSSP-Algorithmus

  * Der bidirektionale Dijkstra wurde im Buch [[http://www.rand.org/pubs/reports/R366/|Linear Programming and Extensions]] von Dantzig vorgestellt.

  * [[http://www.dis.uniroma1.it/~challenge9/download.shtml|Straßennetzwerke]], die im Rahmen der [[http://www.dis.uniroma1.it/~challenge9/|9. DIMACS Implementation Challenge]] zur Verfügung gestellt wurden (u.a. Europe von der PTV AG).

=== A*-Suche ===

  * im Umfeld von KI: [[http://www.jstor.org/stable/2415467|Doran & Michie (1966)]]
  * Originalartikel: [[http://dx.doi.org/10.1109%2FTSSC.1968.300136|Hart, Nilsson & Raphael (1968)]]

=== Überblick zu Speedup-Techniken ===

  * Übersichtsartikel von [[http://dx.doi.org/10.1007/978-3-642-02094-0_7|Delling, Sanders, Schultes & Wagner (2009)]]
  * auch interessant: [[http://research.microsoft.com/en-us/people/goldberg/hwd.pdf|Folien]] von Goldberg zu klassischen und aktuellen Techniken

  * Multilevel-Methoden: [[http://dx.doi.org/10.1007/3-540-48318-7_11|Schulz, Wagner & Weihe (1999)]]
  * Reach-basiertes Routing: [[http://www.siam.org/meetings/alenex04/abstacts/rgutman1.pdf|Gutman (2004)]]
  * Highway-Hierarchies: [[http://dx.doi.org/10.1007/11561071_51|Sanders & Schultes (2005)]]
  * fortgeschrittenes Reach-basiertes Routing: [[http://www.siam.org/proceedings/alenex/2006/alx06_013agoldberg.pdf|Goldberg, Kaplan & Werneck (2006)]]
  * Highway-Node-Routing: [[http://dx.doi.org/10.1007/978-3-540-72845-0_6|Schultes & Sanders (2007)]]
  * Contraction-Hierarchies: [[http://dx.doi.org/10.1007/978-3-540-68552-4_24|Geisberger et al. (2008)]]
  * Entfernungstabellen: [[http://dx.doi.org/10.1007/11841036_71|Sanders & Schules (2006)]]
  * Transit-Knoten Routing: [[http://i11www.ira.uka.de/extra/publications/dhmsw-hpmlr-09.pdf|Delling et al. (2008)]], [[http://www.siam.org/proceedings/alenex/2007/alx07_005basth.pdf|Bast et al. (2007)]], [[http://algo2.iti.kit.edu/schultes/hwy/hhTransitSubmit.pdf|Sanders & Schultes (2008)]]

  * Kanten-Label: [[http://dx.doi.org/10.1007/3-540-48318-7_11|Schulz, Wagner & Weihe (1999)]]
  * SHARC: [[http://www.siam.org/proceedings/alenex/2008/alx08_02bauerr.pdf|Bauer & Delling (2008)]]
  * Landmark A*: [[http://portal.acm.org/citation.cfm?id=1070455|Goldberg & Harrelson (2005)]], [[http://research.microsoft.com/apps/pubs/default.aspx?id=64511|Technical Report]]




\\ 
----

{{page>ae-2010-footer}}