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 textsfDeleteArc that uses a group of auxiliary procedures. We provide the textsfDeleteArc procedure along with the auxiliary procedures, prove correctness of these procedures and evaluate the time complexity. We also consider an example of implementing the textsfDeleteArc procedure on the STAR-machine.

Keywords

MSC

05C20, 05C38, 05C85

Cite this article

@article{cai-110195,
  author  = {Anna Nepomniaschaya},
  title   = {Efficient Parallel Implementation of the Ramalingam Decremental Algorithm for Updating the Shortest Paths Subgraph},
  journal = {Computing and Informatics},
  volume  = {32},
  number  = {2},
  pages   = {331--354},
  year    = {2013},
  issn    = {1335-9150},
  url     = {https://cai.type.sk/content/2013/2/efficient-parallel-implementation-of-the-ramalingam-decremental-algorithm-for-updating-the-shortest-paths-subgraph/}
}
Download .bib