Updating Properties of Directed Acyclic Graphs on a Parallel Random Access Machine

摘要

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 O(log n) time and use (O cu n) processors. These algorithms are efficient when compared to previously known O(log 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 O(log sq n). (Author)