The paper proposes an efficient associative algorithm for dynamic update
of the shortest paths tree of a directed weighted graph after deletion of an
edge. To this end, we use the STAR–machine that simulates the run of associative
(content addressable) parallel systems of the SIMD type with bit–serial (vertical)
processing. We provide a data structure that allows us to perform access to data
by contents. On the STAR–machine, the associative algorithm is represented as
the main procedure *DeleteArcSPT* that uses a group of auxiliary procedures. By
means of the auxiliary procedures, we execute some parts of the associative parallel
algorithm for dynamic update of the shortest paths tree after deleting an arc from
the graph. We prove correctness of the procedure *DeleteArcSPT* and all its parts.
On the STAR–machine, this procedure takes *O(hk)* time, where *h* is the number
of bits required for coding the maximum of the shortest paths weights and *k* is the
number of vertices, whose shortest paths change after deleting an edge from the
given graph.

Abstract

File

nepomniaschaya_a_sh.pdf93.84 KB

Pages

93-106