This list is an incomplete list of abstracts for Ray's journal papers. You can request other abstracts from Ray. You can also download postscript versions of the final submitted versions of the papers.
Several new graph theoretic problems, which arise naturally from existing coloring algorithms, are defined. The complementary High Degree Vertex Removal Problem and Low Degree Vertex Removal Problem are both shown to be NP-complete. The Low Degree Subgraph Problem is defined and shown to be NP-complete, whereas, the ``complementary'' problem for high degree subgraphs was previously shown to be P-complete. Since the obvious sequential algorithms for computing the low degree subgraph and high degree subgraph are based on high degree vertex removal and low degree vertex removal respectively, we find this is an interesting result. The ``greedy'' versions of the vertex removal and subgraph problems are shown to be P-complete. In addition, a natural lexicographic version of the Low Degree Subgraph Problem is shown to be NP-complete.
The potential speedup for SIMD parallel implementations of APL programs is considered. Both analytical and (simulated) empirical studies are presented. The approach is to recognize that nearly 95% of the operators appearing in APL programs are either scalar primitive, reduction or indexing and so the performance of these operators gives a good estimate of the amount of speedup a full program might receive. Substantial speedups are demonstrated for these operators and the empirical evidence accords with the analytical estimates.
A model is proposed that can be used to classify algorithms as inherently sequential. The model captures the internal computations of algorithms. Previous work in complexity theory has focused on the solutions algorithms compute. Direct comparison of algorithms within the framework of the model is possible. The model is useful for identifying hard to parallelize constructs that should be avoided by parallel programmers.
The model's utility is demonstrated via applications to graph searching. A stack breadth-first search (BFS) algorithm is analyzed and proved inherently sequential. The proof technique used in the reduction is a new one. The result for stack BFS sharply contrasts a result showing that a queue based BFS algorithm is in NC. An NC algorithm to compute greedy depth-first search numbers in a dag is presented, and a result proving that a combination search strategy called breadth-depth search is inherently sequential is also given.
Several classes of sequential algorithms to approximate the maximum acyclic subgraph problem are examined. The equivalent feedback arc set problem is NP -complete and there are only a few classes of graphs for which it is known to be in P. Thus, approximation algorithms are very important for this problem. Our goal is to determine how effectively the various sequential algorithms parallelize. Of the sequential algorithms we study, natural decision problems based on several of them are proved P-complete. Parallel implementations using O(log |V|) time and |E| processors on an EREW PRAM exist for the other algorithms. Interestingly, the parallelizable algorithms appear very similar to some of the inherently sequential algorithms. Thus, for approximating the maximum acyclic subgraph problem small algorithmic changes drastically alter parallel complexity, unless NC equals P.
This paper places the optimal tree ranking problem in NC. A ranking is a labeling of the nodes with natural numbers such that if nodes u and v have the same label then there exists another node with a greater label on the path between them. An optimal ranking is a ranking in which the largest label assigned to any node is as small as possible among all rankings. An O(n) sequential algorithm is known. Researchers have speculated that this problem is P-complete. We show that for an n-node tree, one can compute an optimal ranking in O(log n) time using n^2/log n CREW PRAM processors. In fact, our ranking is super critical in that the label assigned to each node is absolutely as small as possible. We achieve these results by showing that a more general problem, which we call the super critical numbering problem , is in NC. No NC algorithm for the super critical tree ranking problem, approximate or otherwise, was previously known; the only known NC algorithm for optimal tree ranking was an approximate one.
The parallel complexity of a search strategy that combines attributes of both breadth-first search and depth-first search is studied. The search called breadth-depth search was defined by Horowitz and Sahni. The search technique has applications in branch-and-bound strategies. Kindervater and Lenstra posed the complexity of this type of search strategy as an open problem. We resolve their question by showing that a natural decision problem based on breadth-depth search is P-complete. Specifically, we prove that if given a graph G = (V,E) either directed or undirected, a start vertex s in V, and two designated vertices u and v in V, then the problem of deciding whether u is visited before v by a breadth-depth search originating from s is P-complete. The search can be based either on vertex numbers or fixed ordered adjacency lists. Our reductions differ for directed/undirected graphs and depending on whether vertex numbers/fixed ordered adjacency lists are used. These results indicate breadth-depth search is highly sequential in nature and probably will not adapt to a fast parallel solution, unless NC equals P.
This paper investigates the parallel complexity of several non-equilibrium growth models. Invasion percolation , Eden growth , ballistic deposition and solid-on-solid growth are all seemingly highly sequential processes that yield self-similar or self-affine random clusters. Nonetheless, we present fast parallel randomized algorithms for generating these clusters. The running times of the algorithms scale as O(log^2 N), where N is the system size, and the number of processors required scale as a polynomial in N. The algorithms are based on fast parallel procedures for finding minimum weight paths; they illuminate the close connection between growth models and self-avoiding paths in random environments. In addition to their potential practical value, our algorithms serve to classify these growth models as less complex than other growth models, such as diffusion-limited aggregation , for which fast parallel algorithms probably do not exist.
An edge ranking of a graph is a labeling of the edges using positive integers such that all paths between two edges with the same label contain an intermediate edge with a higher label. An edge ranking is optimal if the highest label used is as small as possible. The edge-ranking problem has applications in scheduling the manufacture of complex multi-part products; it is equivalent to finding the minimum height edge-separator tree. In this paper we give the first polynomial-time algorithm to find an optimal edge ranking of a tree, placing the problem in P. An interesting feature of the algorithm is an unusual greedy procedure that allows us to narrow an exponential search space down to a polynomial search space containing an optimal solution. An NC algorithm is presented that finds an optimal edge ranking for trees of constant degree. We also prove that a natural decision problem emerging from our sequential algorithm is P-complete.
This paper is concerned with the subclass of graphs called cubic graphs. We survey these graphs and their history. Several classical graph theory results concerning cubic graphs are explained. Graph theory problems whose solutions on cubic graphs are particularly important or interesting are presented both from the sequential and parallel point of view. A new algorithm is presented for the maximal matching problem restricted to cubic graphs. Many miscellaneous facts about cubic graphs are also described. An extensive list of references is provided.
In this paper we examine a number of models that generate random fractals. The models are studied using the tools of computational complexity theory from the perspective of parallel computation. Diffusion limited aggregation and several widely used algorithms for equilibrating the Ising model are shown to be highly sequential; it is unlikely they can be simulated efficiently in parallel. This is in contrast to Mandelbrot percolation that can be simulated in constant parallel time. Our research helps shed light on the intrinsic complexity of these models relative to each other and to different growth processes that have been recently studied using complexity theory. In addition, the results may serve as a guide to simulation physics.
This research note shows subtree isomorphism is in DLOG, and hence NC^2, for nested trees . To our knowledge this result provides the first interesting class of trees for which the problem is in a non-randomized version of NC. We also show that one can determine whether or not an arbitrary tree is a nested tree in DLOG.
Please download the paper.
A parallel algorithm for diffusion-limited aggregation (DLA) is described and analyzed from the perspective of computational complexity. The dynamic exponent z of the algorithm is defined with respect to the probabilistic parallel random-access machine (PRAM) model of parallel computation according to T approximately L^z, where L is the cluster size, T is the running time, and the algorithm uses a number of processors polynomial in L. It is argued that z = D - D_2 / 2, where D is the fractal dimension and D_2 is the second generalized dimension. Simulations of DLA are carried out to measure D_2 and to test scaling assumptions employed in the complexity analysis of the parallel algorithm. It is plausible that the parallel algorithm attains the minimum possible value of the dynamic exponent in which case z characterizes the intrinsic history dependence of DLA.
Please download the paper.
The paper's main contributions are a compendium of problems that are complete for symmetric logarithmic space (SL), a collection of material relating to SL, a list of open problems, and an extension to the number of problems known to be SL-complete. Complete problems are one method of studying SL, a class for which programming is nonintuitive. Our exposition helps make the class SL less mysterious and more accessible to other researchers.
A Prufer code of a labeled free tree with n nodes is a sequence of length n-2 constructed by the following sequential process: for i ranging from 1 to n-2 insert the label of the neighbor of the smallest remaining leaf into the ith position of the sequence, and then delete the leaf. Prufer codes provide an alternative to the usual representation of trees. We present an optimal O(log n) time, n/log n processor EREW-PRAM algorithm for determining the Prufer code of an n-node labeled chain and an O(log n) time, n processor EREW-PRAM algorithm for constructing the Prufer code of an n-node labeled free tree. This resolves an open question posed by Wang, Chen, and Liu.
The k-th power of a graph G is a graph on the same vertex set as G, where a pair of vertices is connected by an edge if they are of distance at most k in G. We study the structure of powers of chordal graphs and the complexity of coloring them. We start by giving new and constructive proofs of the known facts that any power of an interval graph is an interval graph, and that any odd power of a general chordal graph is again chordal. We then show that it is computationally hard to approximately color the even powers of n-vertex chordal graphs within an n^{1/2-epsilon} factor, for any epsilon > 0. We present two exact and closed formulas for the chromatic polynomial for the k-th power of a tree on n vertices. Furthermore, we give an O(kn) algorithm for evaluating the polynomial.
With a rich history and numerous applications, parallel computing has become a very important topic in the field of engineering. We take a look at its history, covering some of the items that are relevant to the current state of parallel programming and parallel machines. We also look at the requirements of programming languages that can be used in conjunction with parallel computer. Then, we look at some of the engineering applications where parallel computing is being utilized to great benefit. We next delve into the theoretical aspects inherent in this field, going over some of the models used in parallel computation, while also describing the complexity classes used. Finally, we cover some statistical physics models and then classify these growth models using the complexity classes introduce.
Computer Science has a brief but rich history. Many important breakthroughs have occurred that were significant due to their intellectual merit, their timing and/or their impact on society. Fortunes had been made and lost, and in some cases, regained. The rapid evolution of the field calls for a survey paper to put some of these breakthroughs in perspective. Each of these new discoveries has helped advance the field in some regard. The depth and breadth of computer science force us to be selective in the results to include. This paper attempts to list discoveries that not only advanced their specific domain, but also the field of computing in general. The breakthroughs discussed are Turing Machines, Moore's Law, recursion, NP-Completeness, the Internet, the Web, high-level programming languages, handheld and wireless devices, and the Human Genome Project.