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

Authors

  • Anna S. Nepomniaschaya Institute of Computational Mathematics and Mathematical Geophysics, Siberian Division of the Russian Academy of Sciences, Novosibirsk

Keywords:

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

Abstract

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.

Downloads

Download data is not yet available.

Downloads

Published

2013-05-23

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://147.213.75.17/ojs/index.php/cai/article/view/1624

Issue

Vol. 32 No. 2 (2013): Computing and Informatics

Section

Articles