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

• Autoři: BRIM Luboš; ČERNÁ Ivana; KRČÁL Pavel; PELÁNEK Radek
• Rok publikování: 2001
• Druh: Článek ve sborníku
• Konference: SOFSEM 2001
• Fakulta / Pracoviště MU: Fakulta informatiky
• Obor: Počítačový hardware a software
• Popis: 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.

Související projekty

• Algoritmy a nástroje pro praktickou verifikaci souběžných systémů
• Nesekvenční modely výpočtů -- kvantové a souběžné distribuované modely výpočetních procesů