Efficient Parallel Implementation of the Ramalingam Decremental Algorithm for Updating the Shortest Paths Subgraph
Keywords:Directed weighted graph, subgraph of the shortest paths, adjacency matrix, decremental algorithm, associative parallel processor, access data by contents, time complexity
AbstractWe propose an efficient parallel implementation of the Ramalingam algorithm for dynamic updating the shortest paths subgraph of a directed weighted graph with a sink after deletion of an edge. To this end, a model of associative (content addressable) parallel systems with vertical processing (the STAR-machine) is used. On the STAR-machine, the Ramalingam decremental algorithm for dynamic updating the shortest paths subgraph is represented as the main procedure DeleteArc that uses a group of auxiliary procedures. We provide the DeleteArc procedure along with the auxiliary procedures, prove correctness of these procedures and evaluate the time complexity. We also consider an example of implementing the DeleteArc procedure on the STAR-machine.
Download data is not yet available.
How to Cite
Nepomniaschaya, A. S. (2013). Efficient Parallel Implementation of the Ramalingam Decremental Algorithm for Updating the Shortest Paths Subgraph. COMPUTING AND INFORMATICS, 32(2), 331–354. Retrieved from http://www.cai.sk/ojs/index.php/cai/article/view/1624