Efficient parallel algorithms and data structures related to trees Page: 2
The following text was automatically extracted from the image on this page using optical character recognition software:
Chen, Calvin Ching-Yuen, Efficet Algoritms and Data Structures RA to Tres.
Doctor of Philosophy (Computer Science), December, 1991, 124 pp., 13 tables, 22
figures, bibliography, 128 titles.
Trees are one of the most fundamental notions in computer science. Serial algorithms for
traversing and manipulating such data structures have been well studied. However, it turns
out that either most of theses algorithms cannot be directly parallelized because the
methods used are inherently sequential in nature, or there are a limited number of
systematic strategies for designing efficient parallel algorithms for problems related to
One of the contributions of this dissertation proposeds a new paradigm, called the
parentheses matching paradigm. We claim that this paradigm is well suited for designing
efficient parallel algorithms for a broad class of nonnumeric problems. To demonstrate its
applicability, we present three cost-optimal parallel algorithms for breadth-first traversal of
general trees, sorting a special class of integers, and coloring an interval graph with the
minimum number of colors.
Although trees as data structures are our major focus of investigations, we consider
associated problems related to graphs and arrays (or lists). For arrays (or lists), we
investigate the class of tree-traversal problems in which we are concerned about how to
store a tree in an array (or list) in parallel such that the data structure has multiple access
paths without memory contentions and conflicts. In this category, we design adaptive,
cost-optimal, parallel algorithms for depth-order (namely pre-, in-, and post-order) and
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/2/: accessed November 17, 2018), University of North Texas Libraries, Digital Library, digital.library.unt.edu; .