How to Employ Reverse Search in Distributed Single-Source Shortest Paths

Investor logo

Warning

This publication doesn't include Faculty of Economics and Administration. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Title in English Distributed LTL Model-Checking Based on Negative Cycle Detection
Authors

BRIM Luboš ČERNÁ Ivana KRČÁL Pavel PELÁNEK Radek

Year of publication 2001
Type Article in Proceedings
Conference SOFSEM 2001
MU Faculty or unit

Faculty of Informatics

Citation
Field Computer hardware and software
Description 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:

You are running an old browser version. We recommend updating your browser to its latest version.