How to Employ Reverse Search in Distributed Single-Source Shortest Paths
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. In SOFSEM 2001. Piestany: Springer, 2001, s. 191-200. LNCS 2234. ISBN 3-540-42912-3. |
Další formáty:
BibTeX
LaTeX
RIS
|
Zá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. |
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ěnil | Změnil: prof. RNDr. Luboš Brim, CSc., učo 197. Změněno: 3. 12. 2001 14:07. |
Anotace |
---|
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. |
Anotace 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 | Název: Algoritmy a nástroje pro praktickou verifikaci souběžných systémů |
Investor: Grantová agentura ČR, Algoritmy a nástroje pro praktickou verifikaci souběžných systémů | |
MSM 143300001, záměr | Název: Nesekvenční modely výpočtů - kvantové a souběžné distribuované modely výpočetních procesů |
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Nesekvenční modely výpočtů -- kvantové a souběžné distribuované modely výpočetních procesů |
VytisknoutZobrazeno: 10. 9. 2024 06:11