Contraction hierarchies

Contraction hierarchies

In applied mathematics, the method of contraction hierarchies is a technique to simplify shortest-path routing by first creating precomputed "contracted" versions of the connection graph. It can be regarded as a special case of highway-node routing.[1]

Contraction hierarchies can be used to generate shortest-path routes much more efficiently than Dijkstra's algorithm or previous highway-node routing approaches,[citation needed] and are used in the OpenTripPlanner software.[2]

References

  1. ^ Robert Geisberger (1 July 2008). "Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks". Institut für Theoretische Informatik Universität Karlsruhe. http://algo2.iti.kit.edu/documents/routeplanning/geisberger_dipl.pdf. Retrieved 2010-12-27. 
  2. ^ "Learn - OpenTripPlanner". http://opentripplanner.com/learn. Retrieved 2010-12-27. 

Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • OpenStreetMap — of Cambridge, England URL …   Wikipedia

  • OpenStreetMap — http://www.openstreetmap.org Motto The Free Wiki World Map …   Deutsch Wikipedia

  • sens — 1. sens [ sɑ̃s ] n. m. • 1080; lat. sensus, de sentire → sentir I ♦ 1 ♦ Faculté d éprouver les impressions que font les objets matériels (⇒ sensation); physiol. Système récepteur unitaire d une modalité spécifique de sensations (correspondant, en …   Encyclopédie Universelle

  • Judaism — /jooh dee iz euhm, day , deuh /, n. 1. the monotheistic religion of the Jews, having its ethical, ceremonial, and legal foundation in the precepts of the Old Testament and in the teachings and commentaries of the rabbis as found chiefly in the… …   Universalium

  • United Kingdom — a kingdom in NW Europe, consisting of Great Britain and Northern Ireland: formerly comprising Great Britain and Ireland 1801 1922. 58,610,182; 94,242 sq. mi. (244,100 sq. km). Cap.: London. Abbr.: U.K. Official name, United Kingdom of Great… …   Universalium

  • KABBALAH — This entry is arranged according to the following outline: introduction general notes terms used for kabbalah the historical development of the kabbalah the early beginnings of mysticism and esotericism apocalyptic esotericism and merkabah… …   Encyclopedia of Judaism

  • china — /chuy neuh/, n. 1. a translucent ceramic material, biscuit fired at a high temperature, its glaze fired at a low temperature. 2. any porcelain ware. 3. plates, cups, saucers, etc., collectively. 4. figurines made of porcelain or ceramic material …   Universalium

  • China — /chuy neuh/, n. 1. People s Republic of, a country in E Asia. 1,221,591,778; 3,691,502 sq. mi. (9,560,990 sq. km). Cap.: Beijing. 2. Republic of. Also called Nationalist China. a republic consisting mainly of the island of Taiwan off the SE coast …   Universalium

  • DÉMONSTRATION (THÉORIE DE LA) — La théorie de la démonstration est la logique de la logique. En contraste avec d’autres sous domaines tels que la théorie des modèles, les grandes questions qui ont tant passionné nos pères ont laissé une trace vivace dans cette discipline, qui… …   Encyclopédie Universelle

  • Life Sciences — ▪ 2009 Introduction Zoology       In 2008 several zoological studies provided new insights into how species life history traits (such as the timing of reproduction or the length of life of adult individuals) are derived in part as responses to… …   Universalium

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”