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...