Efficient parallel implementation of the Ramalingam decremental algorithm for updating the all-pairs shortest paths

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.