Publication details
Distributed Shortest Paths for Directed Graphs with Negative Edge Lengths
| Basic information | |
|---|---|
| Original title: | Distributed Shortest Paths for Directed Graphs with Negative Edge Lengths |
| Authors: | Luboš Brim, Ivana Černá, Pavel Krčál, Radek Pelánek |
| Further information | |
|---|---|
| Citation: | BRIM, Luboš  - ČERNÁ, Ivana - KRČÁL, Pavel - PELÁNEK, Radek. Distributed Shortest Paths for Directed Graphs with Negative Edge Lengths. Brno : FI MU, 2001. 19 pp. Technical Reports, FIMU-RS-2001-01. |
| Original language: | English |
| Field: | Computer hardware and software |
| WWW: |  http://www.fi.muni.cz/informatics/reports/pdf/FIMU-RS-2001-01.pdf |
| Type: | Monograph |
A distributed algorithm for single source shortest path problem in an arbitrary directed graph which can contain negative length cycles is presented. The new algorithm is a label-correcting one and uses a novel way for detection of negative length cycles. It works on a network of processors with disjoint memory that communicate via message passing. Correctness of the algorithm is proved. The algorithm is work-efficient as its worst time complexity is O(n^3/p), where p is the number of processors.
Related projects:
- Algorithms and tools for practical verification of concurrent systems.
- Non-sequential Models of Computing -- Quantum and Concurrent Distributed Models of Computing
