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

BRIM, Luboš, Ivana ČERNÁ, Pavel KRČÁL and Radek PELÁNEK. How to Employ Reverse Search in Distributed Single-Source Shortest Paths (Distributed LTL Model-Checking Based on Negative Cycle Detection). How to Employ Reverse Search in Distributed Single-Source Shortest Paths. In SOFSEM 2001. Piestany: Springer, 2001, p. 191-200. LNCS 2234. ISBN 3-540-42912-3.

Basic information

• Original name: How to Employ Reverse Search in Distributed Single-Source Shortest Paths
• Name (in English): Distributed LTL Model-Checking Based on Negative Cycle Detection
• Authors: BRIM, Luboš, Ivana ČERNÁ, Pavel KRČÁL and Radek PELÁNEK.; How to Employ Reverse Search in Distributed Single-Source Shortest Paths.
• Edition: Piestany, SOFSEM 2001, p. 191-200, LNCS 2234, 2001.
• Publisher: Springer

Other information

• Type of outcome: Proceedings paper
• Field of Study: 20206 Computer hardware and architecture
• Confidentiality degree: is not subject to a state or trade secret
• RIV identification code: RIV/00216224:14330/01:00004501
• Organization unit: Faculty of Informatics
• ISBN: 3-540-42912-3

Abstract

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.

Abstract (in English)

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.

Links

• GA201/00/1023, research and development project: Name: Algoritmy a nástroje pro praktickou verifikaci souběžných systémů

Investor: Czech Science Foundation, Algorithms and tools for practical verification of concurrent systems.

• MSM 143300001, plan (intention): Name: Nesekvenční modely výpočtů - kvantové a souběžné distribuované modely výpočetních procesů

Investor: Ministry of Education, Youth and Sports of the CR, Non-sequential Models of Computing -- Quantum and Concurrent Distributed Models of Computing