Accession Number:

ADA160135

Title:

On Using Inverted Trees for Updating Graph Properties.

Descriptive Note:

Technical rept.,

Corporate Author:

MARYLAND UNIV COLLEGE PARK CENTER FOR AUTOMATION RESEARCH

Personal Author(s):

Report Date:

1985-05-01

Pagination or Media Count:

21.0

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 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.

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE