A new graph triconnectivity algorithm and its parallelization

We present a new algorithm for finding the triconnected components of an undirected graph. The algorithm is based on a method of searching graphs called open ear decomposition. A parallel implementation of the algorithm on a CRCW PRAM runs inO(log² n) parallel time usingO(n+m) processors, wheren is the number of vertices andm is the number of edges in the graph.A preliminary version of this paper was presented at the19th Annual ACM Symposium on Theory of Computing, New York, NY, May 1987.Supported by NSF Grant DCR 8514961.Supported by NSF Grant ECS 8404866 and the Semiconductor Research Corporation Grant 86-12-109.     

Improved asymptotic analysis of the average number of steps performed by the self-dual simplex algorithm

In this paper we analyze the average number of steps performed by the self-dual simplex algorithm for linear programming, under the probabilistic model of spherical symmetry. The model was proposed by Smale. Consider a problem ofn variables withm constraints. Smale established that for every number of constraintsm, there is a constantc(m) such that the number of pivot steps of the self-dual algorithm,(m, n), is less thanc(m)(lnn) ^m(m+1) . We improve upon this estimate by showing that(m, n) is bounded by a function ofm only. The symmetry of the function inm andn implies that(m, n) is in fact bounded by a function of the smaller ofm andn. Parts of this research were done while the author was visiting Stanford University, XEROX- PARC, Carnegie-Mellon University and Northwestern University and was supported in part by the National Science Foundation under Grants MCS-8300984, ECS-8218181 and ECS-8121741.     

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 Computation of Rectilinear Geodesic Voronoi Neighbor in the Presence of Obstacles

In this paper we present an algorithm to compute the rectilinear geodesic voronoi neighbor of an arbitrary query pointqamong a setSofmpoints in the presence of a set ofnvertical line segment obstacles inside a rectangular floor. The distance between a pair of points α and β is the shortest rectilinear distance avoiding the obstacles in and is denoted by δ(α, β). The rectilinear geodesic voronoi neighbor of an arbitrary query pointq,RGVN(q) is the pointp_i ∈ Ssuch that δ(q, p_i) is minimum. The algorithm suggests a preprocessing of the elements of the setsSand inO((m + n)log(m + n)) time such that for an arbitrary query pointq, theRGVNquery can be answered inO(log(m + n)) time. The space required for storing the preprocessed information isO(n + m log m). If the points inSare placed on the boundary of the rectangular floor, a different technique is adopted to decrease the space complexity toO(m + n). This technique works even if the obstacles are rectangles instead of line segments. Finally, the parallelization of the preprocessing steps for the latter algorithm is suggested, which takesO(log³(m + n)) time, usingO((m + n)^1.5/log²(m + n)) processors andO(log(m + n)) query time.     

An optimal algorithm for generating equivalence relations on a linear array of processors

We describe a cost-optimal parallel algorithm for enumerating all partitions (equivalence relations) of the set {1, ...,n}, in lexicographic order. The algorithm is designed to be executed on a linear array of processors. It usesn processors, each having constant size memory and each being responsible for producing one element of a given set partition. Set partitions are generated with constant delay leading to anO(B _n) time solution, whereB _n is the total number of set partitions. The same method can be generalized to enumerate some other combinatorial objects such as variations. The algorithm can be made adaptive, i.e. to run on any prespecified number of processors. To illustrate the model of parallel computation, a simple case of enumerating subsets of the set {1, ...,n}, having at mostm (n) elements is also described.The research is partialy supported by NSERC operating grant OGPIN 007.     

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.     

Parallel Dixon Matrices by Bracket

It is known that the Dixon matrix can be constructed in parallel either by entry or by diagonal. This paper presents another parallel matrix construction, this time by bracket. The parallel by bracket algorithm is the fastest among the three, but not surprisingly it requires the highest number of processors. The method also shows analytically that the Dixon matrix has a total of m(m+1)²(m+2)n(n+1)²(n+2)/36 brackets but only mn(m+1)(n+1)(mn+2m+2n+1)/6 of them are distinct.     

An NC Parallel Algorithm for Edge-Coloring Series–Parallel Multigraphs

Many combinatorial problems can be efficiently solved in parallel for series–parallel multigraphs. The edge-coloring problem is one of a few combinatorial problems for which no NC parallel algorithm has been obtained for series–parallel multigraphs. This paper gives an NC parallel algorithm for the problem on series–parallel multigraphsG. It takesO(log n) time withO(Δn/log n) processors, wherenis the number of vertices and Δ is the maximum degree ofG.     

Deadlock avoidance with a modified banker's algorithm

There are three methods for handling deadlocks in resource allocation systems: deadlock prevention, deadlock avoidance and deadlock detection combined with recovery. Of these three methods deadlock avoidance is preferable in many cases but seldom used on account of its high cost. We present a simple modification of a known deadlock avoidance algorithm, the banker's algorithm, which has a running time (mn ²) in a system consisting ofn processes andm different types of resources. Our modified algorithm gives an amortized worst case running time ofO(mn) under certain likely conditions and in that way it can be considered a competitive method for handling deadlocks. At worst, our algorithm is twice as fast as the banker's algorithm.This work was partly supported by The National Swedish Board for Technical Development (STUF) under contract number 85-3127.     

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.     

Partitioning arrangements of lines II: Applications

In this paper we present efficient deterministic algorithms for various problems involving lines or segments in the plane, using the partitioning algorithm described in a companion paper [A3]. These applications include: (i) anO(m ^2/3 n ^2/3 · log^2/3 n · log^/3 (m/n)+(m+n) logn) algorithm to compute all incidences betweenm points andn lines, where is a constant <3.33; (ii) anO(m ^2/3 n ^2/3 · log^5/3 n · log^/3 (m/n)+(m+n) logn) algorithm to computem faces in an arrangement ofn lines; (iii) anO(n ^4/3 log^(+2)/3 n) algorithm to count the number of intersections in a set ofn segments; (iv) anO(n ^4/3 log^{( + 2)/3} n) algorithm to count red-blue intersections between two sets of segments, and (v) anO(n ^3/2 log^/3 n) algorithm to compute spanning trees with low stabbing number for a set ofn points. We also present an algorithm that, given set ofn points in the plane, preprocesses it, in timeO(nm log^+1/2 n), into a data structure of sizeO(m) forn lognmn ², so that the number of points ofS lying inside a query triangle can be computed inO((n/m) log^3/2 n) time.Work on this paper has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grant DCR-83-20085, and by grants from the Digital Equipment Corporation and the IBM Corporation. A preliminary version of this paper appears in theProceedings of the 5th ACM Symposium on Computational Geometry, 1989, pp. 11–22.     

Constructing disjoint paths on expander graphs

In a typical parallel or distributed computation model processors are connected by a spars interconnection network. To establish open-line communication between pairs of processors that wish to communicate interactively, a set of disjoint paths has to be constructed on the network. Since communication needs vary in time, paths have to be dynamically constructed and destroyed.We study the complexity of constructing disjoint paths between given pairs of vertices on expander interconnection graphs. These graphs have been shown before to possess desirable properties for other communication tasks.We present a sufficient condition for the existence ofKn ^Q edge-disjoint paths connecting any set ofK pairs of vertices on an expander graph, wheren is the number of vertices and<1 is some constant. We then show that the computational problem of constructing these paths lies in the classes Deterministic-P and Random-P C.Furthermore, we show that the set of paths can be constructed in probabilistic polylog time in the parallel-distributed model of computation, in which then participating processors reside in the nodes of the communication graph and all communication is done through edges of the graph. Thus, the disjoint paths are constructed in the very computation model that uses them.Finally, we show how to apply variants of our parallel algorithms to find sets ofvertex-disjoint paths when certain conditions are satisfied.Supported in part by a Weizmann fellowship and by contract ONR N00014-85-C-0731.     

A fast algorithm for scalar Nevanlinna-Pick interpolation

Summary In this paper, we derive a fast algorithm for the scalar Nevanlinna-Pick interpolation. Givenn distinct pointsz _i in the unit disk |z|<1 andn complex numbersw _i satisfying the Pick condition for 1in, the new Nevanlinna-Pick interpolation algorithm requires onlyO(n) arithmetic operations to evaluate the interpolatory rational function at a particular value ofz, in contrast to the classical algorithm which requiresO(n ²) arithmetic operations to compute the so-called Fenyves array (which is inherent in the classical algorithm). The new algorithm bypasses the generation of the Fenyves array to speed up the computation, and also yields a parallel scheme requiring onlyO(logn) arithmetic operations on a concurrent-read, exclusive-write parallel random access machine withn processors. We must remark that the rational functionf(z) computed by the new algorithm is one degree higher than the function computed by the classical algorithm.Supported in part by the US Army Research Office Grant No. DAAL03-91-G-0106     

The complexity and construction of many faces in arrangements of lines and of segments

We show that the total number of edges ofm faces of an arrangement ofn lines in the plane isO(m ^2/3– n ^2/3+2 +n) for any>0. The proof takes an algorithmic approach, that is, we describe an algorithm for the calculation of thesem faces and derive the upper bound from the analysis of the algorithm. The algorithm uses randomization and its expected time complexity isO(m ^2/3– n ^2/3+2 logn+n logn logm). If instead of lines we have an arrangement ofn line segments, then the maximum number of edges ofm faces isO(m ^2/3– n ^2/3+2 +n (n) logm) for any>0, where(n) is the functional inverse of Ackermann's function. We give a (randomized) algorithm that produces these faces and takes expected timeO(m ^2/3– n ^2/3+2 log+n(n) log² n logm).The first author is pleased to acknowledge partial support by the Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862 and the National Science Foundation under Grant CCR-8714565. Work on this paper by the third author has been supported by Office of Naval Research Grant N00014-82-K-0381, by National Science Foundation Grant DCR-83-20085, by grants from the Digital Equipment Corporation, and the IBM Corporation, and by a research grant from the NCRD-the Israeli National Council for Research and Development. A preliminary version of this paper has appeared in theProceedings of the 4th ACM Symposium on Computational Geometry, 1988, pp. 44–55.     

The Padé-Rayleigh-Ritz method for solving large hermitian eigenproblems

We make use of the Padé approximants and the Krylov sequencex, Ax,,...,A ^m–1 x in the projection methods to compute a few Ritz values of a large hermitian matrixA of ordern. This process consists in approaching the poles ofR _x()=((I–A)^–1 x,x), the mean value of the resolvant ofA, by those of [m–1/m]_Rx(), where [m–1/m]_Rx() is the Padé approximant of orderm of the functionR _x(). This is equivalent to approaching some eigenvalues ofA by the roots of the polynomial of degreem of the denominator of [m–1/m]_Rx(). This projection method, called the Padé-Rayleigh-Ritz (PRR) method, provides a simple way to determine the minimum polynomial ofx in the Krylov subspace methods for the symmetrical case. The numerical stability of the PRR method can be ensured if the projection subspacem is sufficiently small. The mainly expensive portion of this method is its projection phase, which is composed of the matrix-vector multiplications and, consequently, is well suited for parallel computing. This is also true when the matrices are sparse, as recently demonstrated, especially on massively parallel machines. This paper points out a relationship between the PRR and Lanczos methods and presents a theoretical comparison between them with regard to stability and parallelism. We then try to justify the use of this method under some assumptions.     

Scheduling Independent Tasks with Deadlines on Semi-identical Processors

Given m semi-identical processors which are parallel processors all working with the same speed but in different time intervals of availability and n independent tasks with deadlines, the problem of constructing a feasible pre-emptive schedule is examined. We present an O (nm log n) time algorithm to construct such a schedule whenever one exists. We show that the number of induced pre-emptions is proportional to the total number of processing intervals and deadlines.     

A select and insert sorting algorithm

A general sorting algorithm, having the well knownO(n ²) algorithmsStraight Insertion Sort andSelection Sort as special cases, is described. This algorithm is analyzed in the case that certain choices in the algorithm are done randomly, and this yields an algorithm that has an average complexity ofO(n ^1.5) and a worst case complexity ofO(n ²). However, making random choices (by some random number generator) is time consuming, and a simple quasi-random scheme is therefore implemented. Test runs indicate that also this version has average complexity ofO(n ^1.5), and it even seems to perform better than the version using real random choices (even if we disregard the time used for the random choices). This version also needs very little administrative overhead, and it therefore compares favourably to many other sorting algorithms for small and medium sized arrays.     

On the construction of weighted time-optimal B-trees

B-trees have been popular data structures since their definition. Their success is due to the fact that a B-tree containingn keys is balanced with a height ofO(logn). However, for a given set of elements and their access frequencies, one can construct many B-trees (possibly with different heights). The average access costs of these trees may vary significantly. An algorithm to construct a weighted time-optimal B-tree is presented. A weighted time-optimal B-tree is one in which the weighted access cost is minimized. A dynamic programming algorithm is used to construct a weighted time-optimal B-tree givenn elements and their weights. The algorithm runs in timeO(mn ³ logn) and has a storage requirement ofO(mn ² logn) wherem is the order of the B-tree andn is the number of keys.This research was supported in part by Texas Advanced Research Grant 1080 and NASA Grant NAG 5–739.     

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.     

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.