Parallel graph algorithms for molecular conformation and tree codes.

摘要

Parallel graph algorithms for molecular conformation and tree encoding problems are proposed in this dissertation. A coarse-grained parallel algorithm for tightening interatomic distance-bounds by applying the tetrangle-inequality is parallelized for the molecular conformation problem.; The proposed algorithm logically partitions the nodes into subsets of equal size (dummy nodes are used for padding if necessary). Node partitioning leads to five classes of quadruples, defined by the distribution of the given quadruple's nodes among the subsets. Empirical tests of the implementation with up to 21 processors demonstrated at least 60% efficiency.; The proposed algorithm is based on one-factorizations of complete graphs and complete 3-uniform hypergraphs. We conjecture that a cyclic one-factorization, not relying on Galois fields, exists for all n ≡ 3 (mod 6). While we were able to construct such factorizations for all n ≡ 3 (mod 6) and n ≤ 63, the general result remains to be proved/disproved.; For tree encoding we define and propose a classification for Prüfer-like codes for labeled trees, parallel algorithms for each class of codes, as well as a number of graph-theoretic results derived from Prüfer-like codes.; We propose a new O(n)-time procedure for encoding a labeled tree of order n into (n − 2)-tuple of node labels, as well as an O(n)-time algorithm for determining the diameter of the tree directly from the code. The new code, as well as existing codes due to Prüfer and Neville are categorized into five classes based on code-construction methods: Continuous Sorted-deletion (Prüfer's code), Continuous Queue-deletion (proposed by the author), Continuous Stack-deletion (Neville's third code), Level-by-level Sorted-deletion (Neville's second code), and Level-by-level Stack-deletion.; Four O(log n)-time EREW PRAM algorithms for computing Prüfer-like codes for four of the five tree-code classes are presented (the algorithms for the fifth class have been published by other authors). The algorithm for Continuous Stack-deletion encoding is work optimal since it requires O(n) work. The algorithms for Level-by-level Sorted-deletion, Level-by-level Stack-deletion, and Queue-deletion require O(n log n) work.; Graph-theoretic results for labeled trees derived using Prüfer-like codes include counting the number of trees on n nodes with exactly l leaves, expected number of nodes in the kth level of a random tree, number of trees on n nodes with the specified subtrees (as well as an algorithm for generating such trees randomly). We have described how to modify the code of a given tree in order to obtain another tree at distance one. (Abstract shortened by UMI.)