Parallel algorithms for analyzing activity networks

Parallel algorithms for analyzing activity networks are proposed which include feasibility test, topological ordering of the events, and computing the earliest and latest start times for all activities and hence identification of the critical activities of the activity network. The first two algorithms haveO(logn) time complexity and the remaining one achievesO(logd log logn) time bound, whered is the diameter of the digraph representing the activity network withn nodes. All these algorithms work on a CRCW PRAM and requireO(n ³) processors.     

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.     

Efficient parallel algorithms for shortest paths in planar digraphs

Efficient parallel algorithms are presented, on the CREW PRAM model, for generating a succinct encoding of all pairs shortest path information in a directed planar graphG with real-valued edge costs but no negative cycles. We assume that a planar embedding ofG is given, together with a set ofq faces that cover all the vertices. Then our algorithm runs inO(log² n) time and employsO(nq+M(q)) processors (whereM(t) is the number of processors required to multiply twot×t matrices inO(logt) time). Let us note here that wheneverq<n then our processor bound is better than the best previous one (M(n)).O(log² n) time,n-processor algorithms are presented for various subproblems, including that of generating all pairs shortest path information in a directedouterplanar graph. Our work is based on the fundamental hammock-decomposition technique of G. Frederickson. We achieve this decomposition inO(logn log*n) parallel time by usingO(n) processors. The hammock-decomposition seems to be a fundamental operation that may help in improving efficiency of many parallel (and sequential) graph algorithms.This work was partially supported by the EEC ESPRIT Basic Research Action No. 3075 (ALCOM) and by the Ministry of Industry, Energy and Technology of Greece.     

Optimal parallel quicksort on EREW PRAM

In this paper, we present parallel quicksort algorithms running inO((n/p+logp) logn) expected time andO((n/p+logp+log logn) logn) deterministic time respectively, and both withO(n) space by usingp processors on EREW PRAM. Whenp=O(n/logn), the cost is optimal, in terms of the product of time and number of processors. These algorithms can be used to obtain parallel algorithms for constructing balanced binary search trees without using sorting algorithms. One of our quicksort algorithms leads to a parallel quickhull algorithm on EREW PRAM.The work of this author was partially supported by a fellowship from the College of Science, Old Dominion University, Norfolk, VA 23529, USA.     

The analysis of a nested dissection algorithm

Summary Nested dissection is an algorithm invented by Alan George for preserving sparsity in Gaussian elimination on symmetric positive definite matrices. Nested dissection can be viewed as a recursive divide-and-conquer algorithm on an undirected graph; it usesseparators in the graph, which are small sets of vertices whose removal divides the graph approximately in half. George and Liu gave an implementation of nested dissection that used a heuristic to find separators. Lipton and Tarjan gave an algorithm to findn ^1/2-separators in planar graphs and two-dimensional finite element graphs, and Lipton, Rose, and Tarjan used these separators in a modified version of nested dissection, guaranteeing bounds ofO (n logn) on fill andO(n ^3/2) on operation count. We analyze the combination of the original George-Liu nested dissection algorithm and the Lipton-Tarjan planar separator algorithm. This combination is interesting because it is easier to implement than the Lipton-Rose-Tarjan version, especially in the framework of existïng sparse matrix software. Using some topological graph theory, we proveO(n logn) fill andO(n ^3/2) operation count bounds for planar graphs, twodimensional finite element graphs, graphs of bounded genus, and graphs of bounded degree withn ^1/2-separators. For planar and finite element graphs, the leading constant factor is smaller than that in the Lipton-Rose-Tarjan analysis. We also construct a class of graphs withn ^1/2-separators for which our algorithm does not achieve anO(n logn) bound on fill.The work of this author was supported in part by the Hertz Foundation under a graduate fellowship and by the National Science Foundation under Grant MCS 82-02948The work of this author was supported in part by the National Science Foundation under Grant MCS 78-26858 and by the Office of Naval Research under Contract N00014-76-C-0688     

The weighted maximum independent set problem in permutation graphs

In this paper, sequential and parallel algorithms are presented to find a maximum independent set with largest weight in a weighted permutation graph. The sequential algorithm, which is designed based on dynamic programming, runs in timeO(nlogn) and requiresO(n) space. The parallel algorithm runs inO(log² n) time usingO(n ³/logn) processors on the CREW PRAM, orO(logn) time usingO(n ³) processors on the CRCW PRAM.     

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.     

A divide-and-conquer algorithm for constructing relative neighborhood graph

AnO(n logn) divide-and-conquer algorithm for finding the relative neighborhood graph RNG(V) of a set V ofn points in Euclidean space is presented. If implemented in parallel, its time complexity isO(n) and it requiresO(logn) 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-line coloring of perfect graphs

Lovász, Saks, and Trotter showed that there exists an on-line algorithm which will color any on-linek-colorable graph onn vertices withO(nlog^(2k–3) n/log^(2k–4) n) colors. Vishwanathan showed that at least (log ^k–1 n/k ^k ) colors are needed. While these remain the best known bounds, they give a distressingly weak approximation of the number of colors required. In this article we study the case of perfect graphs. We prove that there exists an on-line algorithm which will color any on-linek-colorable perfect graph onn vertices withn ^10k/loglogn colors and that Vishwanathan's techniques can be slightly modified to show that his lower bound also holds for perfect graphs. This suggests that Vishwanathan's lower bound is far from tight in the general case.Research partially supported by Office of Naval Research grant N00014-90-J-1206.     

Finding thek smallest spanning trees

We give improved solutions for the problem of generating thek smallest spanning trees in a graph and in the plane. Our algorithm for general graphs takes timeO(m log(m, n)=k ²); for planar graphs this bound can be improved toO(n+k ²). We also show that thek best spanning trees for a set of points in the plane can be computed in timeO(min(k ² n+n logn,k ²+kn log(n/k))). Thek best orthogonal spanning trees in the plane can be found in timeO(n logn+kn log log(n/k)+k ²).     

On graphs preserving rectilinear shortest paths in the presence of obstacles

In physical VLSI design, network design (wiring) is the most time-consuming phase. For solving global wiring problems, we propose to first compute from the layout geometry a graph that preserves all shortest paths between pairs of relevant points, and then to operate on that graph for computing shortest paths, Steiner minimal tree approximations, or the like. For a set of points and a set of simple orthogonal polygons as obstacles in the plane, withn input points (polygon corner or other) altogether, we show how a shortest paths preserving graph of sizeO(n logn) can be computed in timeO(n logn) in the worst case, with spaceO(n). We illustrate the merits of this approach with a simple example: If the length of a longest edge in the graph is bounded by a polynomial inn, an assumption that is clearly fulfilled for graphs derived from VLSI layout geometries, then a shortest path can be computed in timeO(n logn log logn) in the worst case; this result improves on the known best one ofO(n(logn)^3/2).     

Embeddings on a boolean cube

In this paper, we characterize a class of graphs which can be embedded on a boolean cube. Some of the graphs in this class are identified with the well known graphs such asmulti-dimensional mesh of trees, tree of meshes, etc. We suggest (i) an embedding of anr-dimensional mesh of trees ofn ^r (r+1)–rn ^r–1 nodes on a boolean cube of (2n) ^r nodes, and (ii) an embedding of a tree of meshes with 2n ² logn+n ² nodes on a boolean cube withn ² exp₂ (log (2 logn+1)]) nodes.     

Low-diameter graph decomposition is in NC

We obtain the first NC algorithm for the low-diameter graph decomposition problem on arbitrary graphs. Our algorithm runs in O(log⁵(n)) time, and uses O(n²) processors. © 1994 John Wiley & Sons, Inc.     

Maximum weight independent set in trees

Computing a maximum independent set, weighted or unweighted, isNP-hard for general as well as planar graphs. However, polynomial time algorithms do exist for solving this problem on special classes of graphs. In this paper we present an efficient algorithm for computing a maximum weight independent set in trees. A divide and conquer approach based on centroid decomposition of trees is used to compute a maximum weight independent set withinO(n logn) time, wheren is the number of vertices in the tree. We introduce a notion of analternating tree which is crucial in obtaining a new independent set from the previous one.     

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.     

Approximating maximum independent sets by excluding subgraphs

An approximation algorithm for the maximum independent set problem is given, improving the best performance guarantee known toO(n/(logn)²). We also obtain the same performance guarantee for graph coloring. The results can be combined into a surprisingly strongsimultaneous performance guarantee for the clique and coloring problems.The framework ofsubgraph-excluding algorithms is presented. We survey the known approximation algorithms for the independent set (clique), coloring, and vertex cover problems and show how almost all fit into that framework. We show that among subgraph-excluding algorithms, the ones presented achieve the optimal asymptotic performance guarantees.A preliminary version of this paper appeared in [9].Supported in part by National Science Foundation Grant CCR-8902522 and PYI Award CCR-9057488.Research done at Rutgers University. Supported in part by Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) fellowship.     

An optimal pram algorithm for a spanning tree on trapezoid graphs

LetG be a graph withn vertices andm edges. The problem of constructing a spanning tree is to find a connected subgraph ofG withn vertices andn?1 edges. In this paper, we propose anO(logn) time parallel algorithm withO(n/logn), processors on an EREW PRAM for constructing a spanning tree on trapezoid graphs.     

Efficient algorithms for finding minimum spanning trees in undirected and directed graphs

Recently, Fredman and Tarjan invented a new, especially efficient form of heap (priority queue). Their data structure, theFibonacci heap (or F-heap) supports arbitrary deletion inO(logn) amortized time and other heap operations inO(1) amortized time. In this paper we use F-heaps to obtain fast algorithms for finding minimum spanning trees in undirected and directed graphs. For an undirected graph containingn vertices andm edges, our minimum spanning tree algorithm runs inO(m logβ (m, n)) time, improved fromO(mβ(m, n)) time, whereβ(m, n)=min {i|log⁽ⁱ⁾ n ≦m/n}. Our minimum spanning tree algorithm for directed graphs runs inO(n logn + m) time, improved fromO(n log n +m log log log_(m/n+2) n). Both algorithms can be extended to allow a degree constraint at one vertex. Research supported in part by National Science Foundation Grant MCS-8302648. Research supported in part by National Science Foundation Grant MCS-8303139. Research supported in part by National Science Foundation Grant MCS-8300984 and a United States Army Research Office Program Fellowship, DAAG29-83-GO020.     

On Shellsort and the frobenius problem

A boundO(N ^1+1/k ) for the running time of Shellsort, withO(logN) passes, is proved very simply by application of a Frobenius basis withk elements.