ASSOCIATIVE VERSION OF THE RAMALINGAM ALGORITHM FOR DYNAMICALLY UPDATING THE SHORTEST-PATH SUBGRAPH AFTER INSERTING A NEW EDGE INTO A GRAPH

摘要

This paper proposes an efficient parallel implementation of the Ramalingam algorithm for dynamically updating the single-sink shortest-path subgraph of a directed graph after adding an edge to the graph with the use of a model of associative (content addressable) parallel systems with vertical processing (the STAR machine). An associative version of this algorithm is described as the InsertNewArc procedure whose correctness is proved. We also consider the main advantages of the associative version of the Ramalingam incremental algorithm.