Associative version of the Ramalingam incremental algorithm for the dynamic all-pairs shortest-path problem

The paper proposes an associative version of the Ramalingam algorithm for the dynamic update of the all-pairs shortest paths of a directed weighted graph after inserting an edge. To this end, a model of associative (content addressable) parallel systems with vertical processing (the STAR–machine) is used. The associative version of the Ramalingam incremental algorithm is given as procedure InsertEdge. We present an efficient implementation of this procedure on the STAR– machine, prove its correctness and evaluate the time complexity.