The paper proposes an efficient parallel implementation of the Ramalingam algorithm for the dynamic update of the all-pairs shortest paths of a directed weighted graph after deleting an edge. To this end, a model of associative parallel systems with vertical data processing (the STAR-machine) is used. With this model, the...
The paper proposes an associative version of the Ramalingam algorithm for the dynamic update of the all-pairs shortest paths of a directed weighted graph after inserting an edge. To this end, a model of associative (content addressable) parallel systems with vertical processing (the STAR–machine) is used. The associative version of...
In this paper we analyze two procedures for finding a minimal spanning tree of a graph for an abstract associative STAR-machine with bit-serial processing. These procedures are based on the Prim-Dijkstra algorithm and use different graph representations. We prove their correctness, evaluate their complexity and compare them. In addition, we...