Efficient parallel algorithms and data structures related to trees Page: 3
The following text was automatically extracted from the image on this page using optical character recognition software:
level-order (namely breadth-first and breadth-depth) traversals of general trees. All of
these algorithms are designed beginning from the initial concepts and they are robust in the
sense that their performance is independent of input representations.
For graphs, we investigate the class of tree-construction problems in which we consider
how to compute depth-first spanning (DFS), breadth-first spanning (BFS), and breadth-
depth spanning (BDS) trees of an interval graph. Our contributions in this category include
efficient parallel algorithms for finding these trees and exploiting novel characterizations of
We also present a new adaptive, cost-optimal algorithms for the parentheses matching
problem as well as two efficient parallel algorithms for finding the articulation points and
bridges on the DFS tree of an interval graph. All algorithms presented in this dissertation
are designed on the exclusive-read and exclusive-write (EREW) parallel random access
machine (PRAM), which is an abstract model for shared memory parallel computations.
Here’s what’s next.
This dissertation can be searched. Note: Results may vary based on the legibility of text within the document.
Tools / Downloads
Get a copy of this page or view the extracted text.
Citing and Sharing
Basic information for referencing this web page. We also provide extended guidance on usage rights, references, copying or embedding.
Reference the current page of this Dissertation.
Chen, Calvin Ching-Yuen. Efficient parallel algorithms and data structures related to trees, dissertation, December 1991; Denton, Texas. (digital.library.unt.edu/ark:/67531/metadc332626/m1/3/: accessed November 14, 2018), University of North Texas Libraries, Digital Library, digital.library.unt.edu; .