2001
How to Employ Reverse Search in Distributed Single-Source Shortest Paths
BRIM, Luboš, Ivana ČERNÁ, Pavel KRČÁL a Radek PELÁNEKZákladní údaje
Originální název
How to Employ Reverse Search in Distributed Single-Source Shortest Paths
Název anglicky
Distributed LTL Model-Checking Based on Negative Cycle Detection
Autoři
BRIM, Luboš, Ivana ČERNÁ, Pavel KRČÁL a Radek PELÁNEK
How to Employ Reverse Search in Distributed Single-Source Shortest Paths.
How to Employ Reverse Search in Distributed Single-Source Shortest Paths.
Vydání
Piestany, SOFSEM 2001, s. 191-200, LNCS 2234, 2001
Nakladatel
Springer
Další údaje
Typ výsledku
Stať ve sborníku
Obor
20206 Computer hardware and architecture
Utajení
není předmětem státního či obchodního tajemství
Kód RIV
RIV/00216224:14330/01:00004501
Organizační jednotka
Fakulta informatiky
ISBN
3-540-42912-3
Změněno: 3. 12. 2001 14:07, prof. RNDr. Luboš Brim, CSc.
V originále
A distributed algorithm for the single source shortest path problem for directed graphs with arbitrary edge lengths is proposed. The new algorithm is based on relaxations and uses reverse search for inspecting edges and thus avoids using any additional data structures. At the same time the algorithm uses a novel way to recognize a reachable negative-length cycle in the graph which facilitates the scalability of the algorithm.
Anglicky
A distributed algorithm for the single source shortest path problem for directed graphs with arbitrary edge lengths is proposed. The new algorithm is based on relaxations and uses reverse search for inspecting edges and thus avoids using any additional data structures. At the same time the algorithm uses a novel way to recognize a reachable negative-length cycle in the graph which facilitates the scalability of the algorithm.
Návaznosti
| GA201/00/1023, projekt VaV |
| ||
| MSM 143300001, záměr |
|