On Using Inverted Trees for Updating Graph Properties.
Abstract
Fast parallel algorithms are presented for updating connected components and bridges of an undirected graph when a minor change has been made to the graph, such as addition or deletion of vertices and edges. The maching 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 C (n-squared) processors. These algorithms are efficient when compared to previously known algorithms for finding connected components and bridges that require O(log squared n) time and use 0 (n-squared) processors. The previous solution is maintained using an inverted tree (a rooted tree where a node points toward its parent) and after a minor change the new solution is rapidly computed from this tree.
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 1985
- Accession Number
- ADA160135
Entities
People
- I. V. Ramakrishnan
- S. Pawagi
Organizations
- University of Maryland