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.
Publié le : 2013-05-23
Classification:
Directed weighted graph, subgraph of the shortest paths, adjacency matrix, decremental algorithm, associative parallel processor, access data by contents, time complexity,
05C20,05C38, 05C85
@article{cai1624,
author = {Anna S. Nepomniaschaya; Institute of Computational Mathematics and Mathematical Geophysics, Siberian Division of the Russian Academy of Sciences, Novosibirsk},
title = {Efficient Parallel Implementation of the Ramalingam Decremental Algorithm for Updating the Shortest Paths Subgraph},
journal = {Computing and Informatics},
volume = {31},
number = {6},
year = {2013},
language = {en},
url = {http://dml.mathdoc.fr/item/cai1624}
}
Anna S. Nepomniaschaya; Institute of Computational Mathematics and Mathematical Geophysics, Siberian Division of the Russian Academy of Sciences, Novosibirsk. Efficient Parallel Implementation of the Ramalingam Decremental Algorithm for Updating the Shortest Paths Subgraph. Computing and Informatics, Tome 31 (2013) no. 6, . http://gdmltest.u-ga.fr/item/cai1624/