Updating Properties of Directed Acyclic Graphs on a Parallel Random Access Machine.
MARYLAND UNIV COLLEGE PARK CENTER FOR AUTOMATION RESEARCH
Pagination or Media Count:
Fast parallel algorithms are presented for updating the transitive closure, the dominator tree, and a topological ordering of a directed acyclic graph DAG when an incremental change has been made to it. The kinds of changes that are considered here include insertion of a vertex or insertion and deletion 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 Olog n time and use O cu n processors. These algorithms are efficient when compared to previously known Olog sq n time algorithms for initial computation of the above mentioned properties of DAGs. The authors describe a new algorithm for initial computation of the dominator tree of a DAG. Their algorithm improves the processor complexity of a previously known algorithm by a factor of n, but does not affect the time complexity, which remains Olog sq n. Author
- Computer Hardware