On Using Multiple Inverted Trees for Parallel Updating of Graph Properties.
Abstract
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. The kinds of changes that are considered here include insertion of a vertex of 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 in this paper require O(log n) time and use 0(N-cubed) processors. These algorithms are efficient when compared to previously known 0(log-squared of n) time start-over algorithms for initial computation of the above mentioned properties of graphs. The previous solution is maintained in mulple inverted trees (a rooted tree where a child node points toward its parent) and after a minor change the new solution is rapidly recomputed from these trees
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 1985
- Accession Number
- ADA166058
Entities
People
- I. V. Ramakrishnan
- Shaunak Pawagi
Organizations
- University of Maryland