Parallel implementation of the Ramalingam incremental algorithm for dynamic updating the shortest-paths subgraph

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