Efficient Parallel Algorithms for Permutation Graphs

In this paper, we present optimal O(log n) time, O(n/log n) processor EREW PRAM parallel algorithms for finding the connected components, cut vertices, and bridges of a permutation graph. We also present an O(log n) time, O(n) processor, CREW PRAM model parallel algorithm for finding a Breadth First Search (BFS) spanning tree of a permutation graph rooted at vertex 1 and use the same to derive an efficient parallel algorithm for the All Pairs Shortest Path problem on permutation graphs.     

Expected parallel time and sequential space complexity of graph and digraph problems

This paper determines upper bounds on the expected time complexity for a variety of parallel algorithms for undirected and directed random graph problems. For connectivity, biconnectivity, transitive closure, minimum spanning trees, and all pairs minimum cost paths, we prove the expected time to beO(log logn) for the CRCW PRAM (this parallel RAM machine allows resolution of write conflicts) andO(logn · log logn) for the CREW PRAM (which allows simultaneous reads but not simultaneous writes). We also show that the problem of graph isomorphism has expected parallel timeO(log logn) for the CRCW PRAM andO(logn) for the CREW PRAM. Most of these results follow because of upper bounds on the mean depth of a graph, derived in this paper, for more general graphs than was known before. For undirected connectivity especially, we present a new probabilistic algorithm which runs on a randomized input and has an expected running time ofO(log logn) on the CRCW PRAM, withO(n) expected number of processors only. Our results also improve known upper bounds on the expected space required for sequential graph algorithms. For example, we show that the problems of finding connected components, transitive closure, minimum spanning trees, and minimum cost paths have expected sequential spaceO(logn · log logn) on a deterministic Turing Machine. We use a simulation of the CRCW PRAM to get these expected sequential space bounds.     

A Unified Approach to the Parallel Construction of Search Trees

We present a unified parallel algorithm for constructing various search trees. The tree construction is based on a unified scheme, called bottom-level balancing, which constructs a perfectly balanced search tree having a uniform distribution of keys. The algorithm takes O(log log N) time using N/log log N processors on the EREW PRAM model, and O(1) time with N processors on the CREW PRAM model, where N is the number of keys in the tree.     

Expected parallel time and sequential space complexity of graph and digraph problems

This paper determines upper bounds on the expected time complexity for a variety of parallel algorithms for undirected and directed random graph problems. For connectivity, biconnectivity, transitive closure, minimum spanning trees, and all pairs minimum cost paths, we prove the expected time to beO(log logn) for the CRCW PRAM (this parallel RAM machine allows resolution of write conflicts) andO(logn · log logn) for the CREW PRAM (which allows simultaneous reads but not simultaneous writes). We also show that the problem of graph isomorphism has expected parallel timeO(log logn) for the CRCW PRAM andO(logn) for the CREW PRAM. Most of these results follow because of upper bounds on the mean depth of a graph, derived in this paper, for more general graphs than was known before.For undirected connectivity especially, we present a new probabilistic algorithm which runs on a randomized input and has an expected running time ofO(log logn) on the CRCW PRAM, withO(n) expected number of processors only.Our results also improve known upper bounds on the expected space required for sequential graph algorithms. For example, we show that the problems of finding connected components, transitive closure, minimum spanning trees, and minimum cost paths have expected sequential spaceO(logn · log logn) on a deterministic Turing Machine. We use a simulation of the CRCW PRAM to get these expected sequential space bounds.This research was supported by National Science Foundation Grant DCR-85-03251 and Office of Naval Research Contract N00014-80-C-0647.This research was partially supported by the National Science Foundation Grants MCS-83-00630, DCR-8503497, by the Greek Ministry of Research and Technology, and by the ESPRIT Basic Research Actions Project ALCOM.     

Fast Generation of Random Permutations Via Networks Simulation

We consider the problem of generating random permutations with uniform distribution. That is, we require that for an arbitrary permutation π of n elements, with probability 1/n! the machine halts with the i th output cell containing π(i) , for 1 ≤ i ≤ n . We study this problem on two models of parallel computations: the CREW PRAM and the EREW PRAM. The main result of the paper is an algorithm for generating random permutations that runs in O(log log n) time and uses O(n ^1+o(1) ) processors on the CREW PRAM. This is the first o(log n) -time CREW PRAM algorithm for this problem. On the EREW PRAM we present a simple algorithm that generates a random permutation in time O(log n) using n processors and O(n) space. This algorithm outperforms each of the previously known algorithms for the exclusive write PRAMs. The common and novel feature of both our algorithms is first to design a suitable random switching network generating a permutation and then to simulate this network on the PRAM model in a fast way. Received November 1996; revised March 1997.     

Finding least-weight subsequences with fewer processors

By restricting weight functions to satisfy the quadrangle inequality or the inverse quadrangle inequality, significant progress has been made in developing efficient sequential algorithms for the least-weight subsequence problem [10], [9], [12], [16]. However, not much is known on the improvement of the naive parallel algorithm for the problem, which is fast but demands too many processors (i.e., it takesO(log² n) time on a CREW PRAM with n³/logn processors). In this paper we show that if the weight function satisfies the inverse quadrangle inequality, the problem can be solved on a CREW PRAM in O(log² n log logn) time withn/log logn processors, or in O(log² n) time withn logn processors. Notice that the processor-time complexity of our algorithm is much closer to the almost linear-time complexity of the best-known sequential algorithm [12].     

An NC algorithm for finding a minimum weighted completion time schedule on series parallel graphs

We present a parallel algorithm for solving the minimum weighted completion time scheduling problem for transitive series parallel graphs. The algorithm takesO(log² n) time withO(n ³) processors on a CREW PRAM, wheren is the number of vertices of the input graph. This is the first NC algorithm for solving the problem.Research supported in part by NSF Grants CCR-9011214 and CCR-9205982.     

An Optimal Shortest Path Parallel Algorithm for Permutation Graphs

We present an optimal parallel algorithm for the single-source shortest path problem for permutation graphs. The algorithm runs in O(log n) time using O(n/log n) processors on an EREW PRAM. As an application, we show that a minimum connected dominating set in a permutation graph can be found in O(log n) time using O(n/log n) processors.     

On Parallel Integer Merging

The problem of merging two sorted arrays A = (a₁, a₂, ..., a_n1) and B = (b₁, b₂, ..., b_n2) is considered. For input elements that are drawn from a domain of integers [1...s] we present an algorithm that runs in O(log log log s) time using n/log log log s CREW PRAM processors (optimal speed-up) and O(ns^ε) space, where n = n₁ + n₂. For input elements that are drawn from a domain of integers [1...n] we present a second algorithm that runs in O(α(n)) time (where α(n) is the inverse of Ackermann′s function) using n/α(n) CREW PRAM processors and linear space. This second algorithm is non-uniform; however, it can be made uniform at a price of a certain loss of speed, or by using a CRCW PRAM.     

Efficient parallel algorithms forr-dominating set andp-center problems on trees

We develop efficient parallel algorithms for ther-dominating set and thep-center problems on trees. On a concurrent-read exclusive-write PRAM, our algorithm for ther-dominating set problem runs inO(logn log logn) time withn processors. The algorithm for thep-center problem runs inO(log² n log logn) time withn processors.     

A Parallel Algorithm for Partitioning a Point Set to Minimize the Maximum of Diameters

Given a set S of n points in the plane, we consider the problem of partitioning S into two subsets such that the maximum of their diameters is minimized. We present a parallel algorithm to solve this problem that runs in time O(log n) using the CREW PRAM with 0(n²) processors.     

Finding the convex hull of a sorted point set in parallel

We present a parallel algorithm for finding the convex hull of a sorted planar point set. Our algorithm runs in O(log n) time using O(n/log n) processors in the CREW PRAM computational model, which is optimal. One of the techniques we use to achieve these optimal bounds is the use of a parallel data structure which we call the hull tree.     

Optimal algorithms for the single and multiple vertex updating problems of a minimum spanning tree

The vertex updating problem for a minimum spanning tree (MST) is defined as follows: Given a graphG=(V, E _G) and an MSTT forG, find a new MST forG to which a new vertexz has been added along with weighted edges that connectz with the vertices ofG. We present a set of rules that produce simple optimal parallel algorithms that run inO(lgn) time usingn/lgn EREW PRAM processors, wheren=¦V¦. These algorithms employ any valid tree-contraction schedule that can be produced within the stated resource bounds. These rules can also be used to derive simple linear-time sequential algorithms for the same problem. The previously best-known parallel result was a rather complicated algorithm that usedn processors in the more powerful CREW PRAM model. Furthermore, we show how our solution can be used to solve the multiple vertex updating problem: Update a given MST whenk new vertices are introduced simultaneously. This problem is solved inO(lgk·lgn) parallel time using (k·n)/(lgk·lgn) EREW PRAM processors. This is optimal for graphs having (kn) edges.Part of this work was done while P. Metaxas was with the Department of Mathematics and Computer Science, Dartmouth College.     

On Parallel Selection and Searching in Partial Orders: Sorted Matrices

Parallel algorithms for the problems of selection and searching on sorted matrices are formulated. The selection algorithm takesO(lognlog lognlog*n) time withO(n/lognlog*n) processors on an EREW PRAM. This algorithm can be generalized to solve the selection problem on a set of sorted matrices. The searching algorithm takesO(log logn) time withO(n/log logn) processors on a Common CRCW PRAM, which is optimal. We show that no algorithm using at mostnlog^cnprocessors,c≥ 1, can solve the matrix search problem in time faster than Ω(log logn) and that Ω(logn) steps are needed to solve this problem on any model that does not allow concurrent writes.     

Efficient and Scalable PRAM Algorithms for Discrete-Event Simulation of Bounded Degree Networks

We describe two new parallel algorithms, one conservative and another optimistic, for discrete-event simulation on an exclusive-read exclusive-write parallel random-access machine (EREW PRAM). The target physical systems are bounded degree networks which are represented by logic circuits. Employing p processors, our conservative algorithm can simulate up to O(p) independent messages of a system with n logical processes in O(log n) time. The number of processors, p, can be optimally varied in the range 1 ≤ p ≤ n. To identify independent messages, this algorithm also introduces a novel scheme based on a variable size time window. Our optimistic algorithm is designed to reduce the rollback frequency and the memory requirement to save past states and messages. The optimistic algorithm also simulates O(p) earliest messages on a p-processor computer in O(log n) time. To our knowledge, such a theoretical efficiency in parallel simulation algorithms, conservative or optimistic, has been achieved for the first time.     

An efficient parallel strategy for the two-fixed-endpoint Hamiltonian path problem on distance-hereditary graphs

In this paper, we solve the two-fixed-endpoint Hamiltonian path problem on distance-hereditary graphs efficiently in parallel. Let T_d(|V|,|E|) and P_d(|V|,|E|) denote the parallel time and processor complexities, respectively, required to construct a decomposition tree of a distance-hereditary graph G=(V,E) on a PRAM model M_d. We show that this problem can be solved in O(T_d(|V|,|E|)+log|V|) time using O(P_d(|V|,|E|)+(|V|+|E|)/log|V|) processors on M_d. Moreover, if G is represented by its decomposition tree form, the problem can be solved optimally in O(log|V|) time using O((|V|+|E|)/log|V|) processors on an EREW PRAM. We also obtain a linear-time algorithm which is faster than the previous known O(|V|³) sequential algorithm.     

An efficient parallel algorithm for the efficient domination problem on distance-hereditary graphs

In the literature, there are quite a few sequential and parallel algorithms for solving problems on distance-hereditary graphs. With an n-vertex and m-edge distance-hereditary graph G, we show that the efficient domination problem on G can be solved in O(log/sup 2/ n) time using O(n + m) processors on a CREW PRAM. Moreover, if a binary tree representation of G is given, the problem can be optimally solved in O(log n) time using O(n/log n) processors on an EREW PRAM.     

Parallel algorithms for arrangements

We give the first efficient parallel algorithms for solving the arrangement problem. We give a deterministic algorithm for the CREW PRAM which runs in nearly optimal bounds ofO (logn log^* n) time andn ²/logn processors. We generalize this to obtain anO (logn log^* n)-time algorithm usingn ^d /logn processors for solving the problem ind dimensions. We also give a randomized algorithm for the EREW PRAM that constructs an arrangement ofn lines on-line, in which each insertion is done in optimalO (logn) time usingn/logn processors. Our algorithms develop new parallel data structures and new methods for traversing an arrangement.This work was supported by the National Science Foundation, under Grants CCR-8657562 and CCR-8858799, NSF/DARPA under Grant CCR-8907960, and Digital Equipment Corporation. A preliminary version of this paper appeared at the Second Annual ACM Symposium on Parallel Algorithms and Architectures [3].     

An optimal parallel algorithm for computing cut vertices and blocks on interval graphs

In this paper, a parallel algorithm is presented to find all cut-vertices and blocks of an interval graph. If the list of sorted end points of the intervals of an interval graph is given then the proposed algorithm takes O(log n) time and O(n/log n) processors on an EREW PRAM, if the sorted list is not given then the time and processors complexities are respectively O(log n) and O(n).     

Efficient parallel algorithms forr-dominating set andp-center problems on trees

We develop efficient parallel algorithms for ther-dominating set and thep-center problems on trees. On a concurrent-read exclusive-write PRAM, our algorithm for ther-dominating set problem runs inO(logn log logn) time withn processors. The algorithm for thep-center problem runs inO(log² n log logn) time withn processors.Xin He was supported in part by an Ohio State University Presidential Fellowship, and by the Office of Research and Graduate Studies of Ohio State University. Yaacov Yesha was supported in part by the National Science Foundation under Grant No. DCR-8606366.