Distributed Shortest Paths for Directed Graphs with Negative Edge Lengths
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F01%3A00004836" target="_blank" >RIV/00216224:14330/01:00004836 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
Distributed Shortest Paths for Directed Graphs with Negative Edge Lengths
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
B - Specialist book
CEP classification
JC - Computer hardware and software
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GA201%2F00%2F1023" target="_blank" >GA201/00/1023: Algorithms and tools for practical verification of concurrent systems</a><br>
Continuities
Z - Vyzkumny zamer (s odkazem do CEZ)
Others
Publication year
2001
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
ISBN
—
Number of pages
19
Publisher name
FI MU
Place of publication
Brno
UT code for WoS book
—