ON USING MULTIPLE INVERTED TREES FOR PARALLEL UPDATING OF GRAPH PROPERTIES.

Fast parallel algorithms are presented for updating the distance matrix, shortest paths for all pairs and biconnected components for an undirected graph and the topological ordering of vertices of a directed acyclic graph when an incremental change has been made to the graph. Changes that are considered include insertion of a vertex or insertion and deletion of an edge or a change in the weight of an edge. The machine model used is a parallel random access machine which allows simultaneous reads but prohibits simultaneous writes into the same memory location. The algorithms described require O(log n) time and use O(n**3) processors. These algorithms are efficient when compared to previously known O(log**2n) time start-over algorithms for initial computation of the above mentioned properties of graphs. The previous solution is maintained in multiple inverted trees (a rooted tree where a child node points towards its father) after a minor change the new solution is rapidly recomputed from these trees.