On Using Inverted Trees for Updating Graph Properties.
MARYLAND UNIV COLLEGE PARK CENTER FOR AUTOMATION RESEARCH
Pagination or Media Count:
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 Olog 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.
- Theoretical Mathematics