A Parallel Reduction of Hamiltonian Cycle to Hamiltonian Path in Tournaments

We propose a parallel algorithm which reduces the problem of computing Hamiltonian cycles in tournaments to the problem of computing Hamiltonian paths. The running time of our algorithm is O(log n) using O(n²/log n) processors on a CRCW PRAM, and O(log n log log n) on an EREW PRAM using O(n²/log n log log n) processors. As a corollary, we obtain a new parallel algorithm for computing Hamiltonian cycles in tournaments. This algorithm can be implemented in time O(log n) using O(n²/log n) processors in the CRCW model and in time O(log²n) with O(n²/log n log log n) processors in the EREW model.     

Parallel algorithms for permutation graphs

In this paper, parallel algorithms are presented for solving some problems on permutation graphs. The coloring problem is solved inO(log² n) time usingO(n ³/logn) processors on the CREW PRAM, orO(logn) time usingO(n ³) processors on the CRCW PRAM. The weighted clique problem, the weighted independent set problem, the cliques cover problem, and the maximal layers problem are all solved with the same complexities. We can also show that the longest common subsequence problem belongs to the class NC.     

Optimal Sequential and Parallel Algorithms to Compute All Cut Vertices on Trapezoid Graphs

In this paper, a sequential algorithm is presented to find all cut-vertices on trapezoid graphs. To every trapezoid graph G there is a corresponding trapezoid representation. If all the 4n corner points of n trapezoids, in a trapezoid representation of a trapezoid graph G with n vertices, are given, then the proposed sequential algorithm runs in O(n) time. Parallel implementation of this algorithm can be done in O(log n) time using O(n/ log n) processors on an EREW PRAM model.     

A Randomized Parallel Algorithm for Planar Graph Isomorphism

We present a parallel randomized algorithm running on aCRCW PRAM, to determine whether two planar graphs are isomorphic, and if so to find the isomorphism. We assume that we have a tree of separators for each planar graph (which can be computed by known algorithms inO(log² n) time withn^{1 + ε}processors, for any ε > 0). Ifnis the number of vertices, our algorithm takesO(log(n)) time with processors and with a probability of failure of 1/nat most. The algorithm needs 2 · log(m) − log(n) + O(log(n)) random bits. The number of random bits can be decreased toO(log(n)) by increasing the number of processors ton^{3/2 + ε}, for any ε > 0. Our parallel algorithm has significantly improved processor efficiency, compared to the previous logarithmic time parallel algorithm of Miller and Reif (Siam J. Comput.20(1991), 1128–1147), which requiresn⁴randomized processors orn⁵deterministic processors.     

A fast and simple randomized parallel algorithm for the maximal independent set problem

A simple parallel randomized algorithm to find a maximal independent set in a graph G = (V, E) on n vertices is presented. Its expected running time on a concurrent-read concurrent-write PRAM with O(|E|d_max) processors is O(log n), where d_max denotes the maximum degree. On an exclusive-read exclusive-write PRAM with O(|E|) processors the algorithm runs in O(log²n). Previously, an O(log⁴n) deterministic algorithm was given by Karp and Wigderson for the EREW-PRAM model. This was recently (independently of our work) improved to O(log²n) by M. Luby. In both cases randomized algorithms depending on pairwise independent choices were turned into deterministic algorithms. We comment on how randomized combinatorial algorithms whose analysis only depends on d-wise rather than fully independent random choices (for some constant d) can be converted into deterministic algorithms. We apply a technique due to A. Joffe (1974) and obtain deterministic construction in fast parallel time of various combinatorial objects whose existence follows from probabilistic arguments.     

On parallel hashing and integer sorting

The problem of sorting n integers from a restricted range [1…m], where m is a superpolynomial in n, is considered. An o(n log n) randomized algorithm is given. Our algorithm takes O(n log log m) expected time and O(n) space. (Thus, for m = n^polylog(n) we have an O(n log log n) algorithm.) The algorithm is parallelizable. The resulting parallel algorithm achieves optimal speedup. Some features of the algorithm make us believe that it is relevant for practical applications. A result of independent interest is a parallel hashing technique. The expected construction time is logarithmic using an optimal number of processors, and searching for a value takes O(1) time in the worst case. This technique enables drastic reduction of space requirements for the price of using randomness. Applicability of the technique is demonstrated for the parallel sorting algorithm and for some parallel string matching algorithms. The parallel sorting algorithm is designed for a strong and nonstandard model of parallel computation. Efficient simulations of the strong model on a CRCW PRAM are introduced. One of the simulations even achieves optimal speedup. This is probably the first optimal speedup simulation of a certain kind.     

Triply-Logarithmic Parallel Upper and Lower Bounds for Minimum and Range Minima over Small Domains

We consider the problem of computing the minimum ofnvalues, and several well-known generalizations [prefix minima, range minima, and all nearest smaller values (ANSV)] for input elements drawn from the integer domain [1···s], wheres ≥ n. In this article we give simple and efficient algorithms for all of the preceding problems. These algorithms all takeO(log log log s) time using an optimal number of processors andO(ns^ε) space (for constant ε < 1) on the COMMON CRCW PRAM. The best known upper bounds for the range minima and ANSV problems were previouslyO(log log n) (using algorithms for unbounded domains). For the prefix minima and for the minimum problems, the improvement is with regard to the model of computation. We also prove a lower bound of Ω(log log n) for domain sizes = 2^{Ω(log n log log n)}. Since, forsat the lower end of this range, log log n = Ω(log log log s), this demonstrates that any algorithm running ino(log log log s) time must restrict the range ofson which it works.     

Binary tree algebraic computation and parallel algorithms for simple graphs

In this paper we define the binary tree algebraic computation (BTAC) problem and develop an efficient parallel algorithm for solving this problem. A variety of graph problems (minimum covering set, minimum r-dominating set, maximum matching set, etc.) for trees and two terminal series parallel (TTSP) graphs can be converted to instances of the BTAC problem. Thus efficient parallel algorithms for these problems are obtained systematically by using the BTAC algorithm. The parallel computation model is an exclusive read exclusive write PRAM. The algorithms for tree problems run in O(log n) time with O(n) processors. The algorithms for TTSP graph problems run in O(log m) time with O(m) processors where n (m) is the number of vertices (edges) in the input graph. These algorithms are within an O(log n) factor of optimal.     

The average performance of a parallel stable marriage algorithm

In this paper, Tseng and Lee's parallel algorithm to solve the stable marriage prolem is analyzed. It is shown that the average number of parallel proposals of the algorithm is of ordern by usingn processors on a CREW PRAM, where each parallel proposal requiresO(loglog(n) time on CREW PRAM by applying the parallel selection algorithms of Valiant or Shiloach and Vishkin. Therefore, our parallel algorithm requiresO(nloglog(n)) time. The speed-up achieved is log(n)/loglog(n) since the average number of proposals required by applying McVitie and Wilson's algorithm to solve the stable marriage problem isO(nlog(n)).     

Parallel and On-Line Graph Coloring

We discover a surprising connection between graph coloring in two orthogonal paradigms: parallel and on-line computing. We present a randomized on-line coloring algorithm with a performance ratio ofO(n/log n), an improvement of factor over the previous best known algorithm of Vishwanathan. Also, from the same principles, we construct a parallel coloring algorithm with the same performance ratio, for the first such result. As a byproduct, we obtain a parallel approximation for the independent set problem.     

Efficient Preprocessing of Simple Binary Pattern Forests

Multipattern matching in trees is fundamental to a variety of programming language systems. A bottleneck in this connection has been the combinatorial problem of constructing the immediate subsumption tree for a simple binary pattern forest. We reduce the complexity of this problem fromO(n²) time andO(n²) space toO(n log n) time andO(n) space. Such a result was conjectured possible in 1982 by C. Hoffmann and J. O'Donnell (J. Assoc. Comput. Mach.29(1) (1982), 68–95) and in 1992 finding it was called a main open problem by J. Cai, R. Paige, and R. Tarjan (J. Theoret. Comput. Sci.106(1992), 21–60).     

Optimally Computing the Shortest Weakly Visible Subedge of a Simple Polygon

Given ann-vertex simple polygonP, the problem of computing the shortest weakly visible subedge ofPis that of finding a shortest line segmentson the boundary ofPsuch thatPis weakly visible froms(ifsexists). In this paper, we present new geometric observations that are useful for solving this problem. Based on these geometric observations, we obtain optimal sequential and parallel algorithms for solving this problem. Our sequential algorithm runs inO(n) time, and our parallel algorithm runs inO(log n) time usingO(n/log n) processors in the CREW PRAM computational model. Using the previously best known sequential algorithms to solve this problem would takeO(n²) time. We also give geometric observations that lead to extremely simple and optimal algorithms for solving, both sequentially and in parallel, the case of this problem where the polygons are rectilinear.     

Efficient Algorithms for Finding a Core of a Tree with a Specified Length

Acoreof a graphGis a pathPinGthat is central with respect to the property of minimizingd(P)=∑_v∈V(G)d(v, P), whered(v, P) is the distance from vertexvto pathP. This paper presents efficient algorithms for finding a core of a tree with a specified length. The sequential algorithm runs inO(n log n) time, wherenis the size of the tree. The parallel algorithm runs inO(log²n) time usingO(n) processors on an EREW PRAM model.     

An Efficient Algorithm for a Sparse k-Edge-Connectivity Certificate

We present an efficient algorithm for finding a sparse k-edge-connectivity certificate of a multigraph G. Our algorithm runs in O((log kn)(log k)²(log n)²) time using O(k(n + m′)) processors on an ARBITRARY CRCW PRAM, where n and m′ stand for the numbers of vertices in G and edges in the simplified graph of G, respectively.     

Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane

An intersection graph of rectangles in the (x, y)-plane with sides parallel to the axes is obtained by representing each rectangle by a vertex and connecting two vertices by an edge if and only if the corresponding rectangles intersect. This paper describes algorithms for two problems on intersection graphs of rectangles in the plane. One is an O(n log n) algorithm for finding the connected components of an intersection graph of n rectangles. This algorithm is optimal to within a constant factor. The other is an O(n log n) algorithm for finding a maximum clique of such a graph. It seems interesting that the maximum clique problem is polynomially solvable, because other related problems, such as the maximum stable set problem and the minimum clique cover problem, are known to be NP-complete for intersection graphs of rectangles. Furthermore, we briefly show that the k-colorability problem on intersection graphs of rectangles is NP-complete.     

Fast Deterministic Processor Allocation

Interval allocation has been suggested as a possible formalization for the PRAM of the (vaguely defined) processor allocation problem, which is of fundamental importance in parallel computing. The interval allocation problem is, given n nonnegative integers x₁, . . ., x_n, to allocate n nonoverlapping subarrays of sizes x₁, . . ., x_n from within a base array of O(Σⁿ_j=1x_j) cells. We show that interval allocation problems of size n can be solved in O((log log n)³) time with optimal speedup on a deterministic CRCW PRAM. In addition to a general solution to the processor allocation problem, this implies an improved deterministic algorithm for the problem of approximate summation. For both interval allocation and approximate summation, the fastest previous deterministic algorithms have running times of Θ(log n/log log n). We describe an application to the problem of computing the connected components of an undirected graph. Finally we show that there is a nonuniform deterministic algorithm that solves interval allocation problems of size n in O(log log n) time with optimal speedup.     

The Parallel Simplicity of Compaction and Chaining

Given a set of values x₁, x₂,..., x_n, of which k are nonzero, the compaction problem is the problem of moving the nonzero elements into the first k consecutive memory locations. The chaining problem asks that the nonzero elements be put into a linked list. One can in addition require that the elements remain in the same order, leading to the problems of ordered compaction and ordered chaining, respectively. This paper introduces a technique involving perfect hash functions that leads to a deterministic algorithm for ordered compaction running on a CRCW PRAM in time O(log k/log log n) using n processors. A matching lower bound for unordered compaction is given. The ordered chaining problem is shown to be solvable in time O(α(k)) with n processors (where α is a functional inverse of Ackermann′s function) and unordered chaining is shown to he solvable in constant time with n processors when k < n^{1/4− ε}.     

Optimally Cutting a Surface into a Disk

We consider the problem of cutting a subset of the edges of a polyhedral manifold surface, possibly with boundary, to obtain a single topological disk, minimizing either the total number of cut edges or their total length. We show that this problem is NP-hard in general, even for manifolds without boundary and for punctured spheres. We also describe an algorithm with running time n ^O(g+k), where n is the combinatorial complexity, g is the genus, and k is the number of boundary components of the input surface. Finally, we describe a greedy algorithm that outputs a O(log² g)-approximation of the minimum cut graph in O(g ² n log n) time.     

A parallel search algorithm for directed acyclic graphs

A parallel algorithm for depth-first searching of a directed acyclic graph (DAG) on a shared memory model of a SIMD computer is proposed. The algorithm uses two parallel tree traversal algorithms, one for the preorder traversal and the other for therpostorder traversal of an ordered tree. Each of these traversal algorithms has a time complexity ofO(logn) whenO(n) processors are used,n being the number of vertices in the tree. The parallel depth-first search algorithm for a directed acyclic graphG withn vertices has a time complexity ofO((logn)²) whenO(n ^2.81/logn) processors are used.     

Enclosing a Set of Objects by Two Minimum Area Rectangles

In this paper, we face the problem of computing an enclosing pair of axis-parallel rectangles of a set of polygonal objects in the plane, serving as a simple container. We propose anO(nα(n)log n) worst-case time algorithm, where α( ) is the inverse Ackermann's function, for finding, given a setMof points, segments and polygons defined bynvertices, a pair of axis-parallel rectangles (s, t) such thats∪tencloses all objects inMand area(s)+area(t) is minimum. The algorithm works inO(nα(n) log log n) worst-case space. Moreover, we prove an Ω(n log n) lower bound for the one-dimensional version of the problem. We also show that for the special case of enclosing a set of polygons with axis-parallel sides, our algorithm runs in optimal worst-case timeO(n log n), using worst-case spaceO(n log log n).