2001
How to Employ Reverse Search in Distributed Single-Source Shortest Paths
BRIM, Luboš; Ivana ČERNÁ; Pavel KRČÁL and Radek PELÁNEKBasic 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.
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
Changed: 3/12/2001 14:07, prof. RNDr. Luboš Brim, CSc.
In the original language
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.
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 |
| ||
| MSM 143300001, plan (intention) |
|