An associative version of the Ramalingam decremental algorithm for the dynamic all-pairs shortest-path problem

This paper proposes an efficient parallel representation 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 processing (the STAR-machine) is used. The associative version is given as a group of algorithms that provide an efficient parallel execution on the STAR-machine of different parts of the Ramalingam decremental algorithm. We also present the main advantages of the associative version of the Ramalingam decremental algorithm for the dynamic update of the all-pairs shortest paths. In the Appendix, we propose a special technique being used in the associative parallel algorithm for finding affected vertices after the edge deletion.