Improvement of shortest path algorithms through graph partitioning
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F11%3A00183405" target="_blank" >RIV/68407700:21240/11:00183405 - isvavai.cz</a>
Výsledek na webu
—
DOI - Digital Object Identifier
—
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Improvement of shortest path algorithms through graph partitioning
Popis výsledku v původním jazyce
Route planning problem occurs often in many practical areas of life including problem of finding of optimal paths in road networks. This paper presents an algorithm based upon traditional graph algorithms, like the Dijkstra's shortest path algorithm butit takes advantage of the specific properties of a road network graph. Presented modification of algorithm partitions a given graph into smaller components, it results in efficient execution even for large-scale graphs. Searching in smaller components still guarantee optimality of solution.
Název v anglickém jazyce
Improvement of shortest path algorithms through graph partitioning
Popis výsledku anglicky
Route planning problem occurs often in many practical areas of life including problem of finding of optimal paths in road networks. This paper presents an algorithm based upon traditional graph algorithms, like the Dijkstra's shortest path algorithm butit takes advantage of the specific properties of a road network graph. Presented modification of algorithm partitions a given graph into smaller components, it results in efficient execution even for large-scale graphs. Searching in smaller components still guarantee optimality of solution.
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
IN - Informatika
OECD FORD obor
—
Návaznosti výsledku
Projekt
—
Návaznosti
Z - Vyzkumny zamer (s odkazem do CEZ)
Ostatní
Rok uplatnění
2011
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název statě ve sborníku
Proceedings of International Conference PRESENTATION of MATHEMATICS '11
ISBN
978-80-7372-773-4
ISSN
—
e-ISSN
—
Počet stran výsledku
7
Strana od-do
131-137
Název nakladatele
Technická univerzita
Místo vydání
Liberec
Místo konání akce
Liberec
Datum konání akce
20. 10. 2011
Typ akce podle státní příslušnosti
EUR - Evropská akce
Kód UT WoS článku
—