Publication details
How to Employ Reverse Search in Distributed Single
-Source Shortest Paths
| Basic information | |
|---|---|
| Original title: | How to Employ Reverse Search in Distributed Single-Source Shortest Paths |
| Title in English: | Distributed LTL Model-Checking Based on Negative Cycle Detection |
| Authors: | Luboš Brim, Ivana Černá, Pavel Krčál, Radek Pelánek |
| Inferior responsibility: | How to Employ Reverse Search in Distributed Single-Source Shortest Paths |
| Further information | |
|---|---|
| Citation: | BRIM, Luboš - ČERNÁ, Ivana - KRČÁL, Pavel - PELÁNEK, Radek. How to Employ Reverse Search in Distributed Single-Source Shortest Paths. In SOFSEM 2001. Piestany : Springer, 2001. ISBN 3-540-42912-3, pp. 191-200. Piestany, Slovensko. |
| Field: | Computer hardware and software |
| Type: | Article in Proceedings |
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.
Related projects:
- Algorithms and tools for practical verification of concurrent systems.
- Non-sequential Models of Computing -- Quantum and Concurrent Distributed Models of Computing
