Parallel Algorithms for Detection of Negative Cycles
by
Luboš Brim,
Ivana Černá,
Lukáš Hejtmánek,
This is a full version of the paper presented at PARCO 2003. July 2003, 14 pages.
FIMU-RS-2003-04.
Available as Postscript,
PDF.
Abstract:
Several new parallel algorithms for the single source shortest paths
and for the negative cycle detection problems on directed graphs with
real edge weights and given by adjacency list are developed, analysed,
and experimentally compared. The algorithms are to be performed on
clusters of workstations that communicate via a message passing
mechanism.