Parallel implementation of the Ramalingam decremental algorithm for dynamic updating the single-sink shortest paths subgraph

We propose an efficient parallel implementation of the Ramalingam algorithm for dynamic updating the single-sink shortest paths subgraph of a directed weighted graph after deletion of an edge on a model of associative (content addressable) parallel systems with vertical processing (the STAR-machine). The associative version of the Ramalingam decremental algorithm for updating the shortest paths subgraph is given as procedure DeleteEdge, whose correctness is proved and the time complexity is evaluated. We compare implementations of the Ramalingam decremental algorithm and its associative version and present the main advantages of the associative version.