Abstract

The paper proposes an efficient parallel implementation of the Ramalingam algorithm for the dynamic update of the all-pairs shortest paths of a directed weighted graph after deleting an edge. To this end, a model of associative parallel systems with vertical data processing (the STAR-machine) is used. With this model, the Ramalingam decremental algorithm for the dynamic update of the all-pairs shortest paths is represented as the main procedure DeleteEdge that uses a group of auxiliary procedures to perform its different parts. We provide the procedure DeleteEdge along with auxiliary procedures, prove the correctness of these procedures and evaluate the time complexity.

DOI
10.31144/bncc.cs.2542-1972.2018.n42.p41-60
File
nepomn.pdf243.49 KB
Issue
Pages
41-60