Efficient Parallel Implementation of the Ramalingam Decremental Algorithm for Updating the Shortest Paths Subgraph

In: Computing and Informatics, vol. 32, no. 2

A.s. Nepomniaschaya

Details:

Year, pages: 2013, 331 - 354

Keywords:

Directed weighted graph, subgraph of the shortest paths, adjacency matrix, decremental algorithm, associative parallel processor, access data by contents, time complexity

About article:

We 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.

How to cite:

ISO 690:

Nepomniaschaya, A. 2013. Efficient Parallel Implementation of the Ramalingam Decremental Algorithm for Updating the Shortest Paths Subgraph. In Computing and Informatics, vol. 32, no.2, pp. 331-354. 1335-9150.

APA:

Nepomniaschaya, A. (2013). Efficient Parallel Implementation of the Ramalingam Decremental Algorithm for Updating the Shortest Paths Subgraph. Computing and Informatics, 32(2), 331-354. 1335-9150.