Accession Number:

ADA162954

Title:

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

Descriptive Note:

Technical rept.,

Corporate Author:

MARYLAND UNIV COLLEGE PARK CENTER FOR AUTOMATION RESEARCH

Personal Author(s):

Report Date:

1985-09-01

Pagination or Media Count:

24.0

Abstract:

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

Subject Categories:

  • Computer Hardware

Distribution Statement:

APPROVED FOR PUBLIC RELEASE