Sieve algorithms for perfect power testing

A positive integern is a perfect power if there exist integersx andk, both at least 2, such thatn=x ^k . The usual algorithm to recognize perfect powers computes approximatekth roots forklog ₂ n, and runs in time O(log³ n log log logn).First we improve this worst-case running time toO(log³ n) by using a modified Newton's method to compute approximatekth roots. Parallelizing this gives anNC ² algorithm.Second, we present a sieve algorithm that avoidskth-root computations by seeing if the inputn is a perfectkth power modulo small primes. Ifn is chosen uniformly from a large enough interval, the average running time isO(log² n).Third, we incorporate trial division to give a sieve algorithm with an average running time ofO(log² n/log² logn) and a median running time ofO(logn).The two sieve algorithms use a precomputed table of small primes. We give a heuristic argument and computational evidence that the largest prime needed in this table is (logn)^1+O(1); assuming the Extended Riemann Hypothesis, primes up to (logn)^2+O(1) suffice. The table can be computed in time roughly proportional to the largest prime it contains.We also present computational results indicating that our sieve algorithms perform extremely well in practice.This work forms part of the second author's Ph.D. thesis at the University of Wisconsin-Madison, 1991. This research was sponsored by NSF Grants CCR-8552596 and CCR-8504485.     

Optimal parallel algorithms for multiple updates of minimum spanning trees

Parallel updates of minimum spanning trees (MSTs) have been studied in the past. These updates allowed a single change in the underlying graph, such as a change in the cost of an edge or an insertion of a new vertex. Multiple update problems for MSTs are concerned with handling more than one such change. In the sequential case multiple update problems may be solved using repeated applications of an efficient algorithm for a single update. However, for efficiency reasons, parallel algorithms for multiple update problems must consider all changes to the underlying graph simultaneously. In this paper we describe parallel algorithms for updating an MST whenk new vertices are inserted or deleted in the underlying graph, when the costs ofk edges are changed, or whenk edge insertions and deletions are performed. For multiple vertex insertion update, our algorithm achieves time and processor bounds ofO(log n·logk) and nk/(logn·logk), respectively, on a CREW parallel random access machine. These bounds are optimal for dense graphs. A novel feature of this algorithm is a transformation of the previous MST andk new vertices to a bipartite graph which enables us to obtain the above-mentioned bounds.     

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.     

Parallel construction of binary trees with near optimal weighted path length

We present parallel algorithms to construct binary trees with almost optimal weighted path length. Specifically, assuming that weights are normalized (to sum up to one) and error refers to the (absolute) difference between the weighted path length of a given tree and the optimal tree with the same weights, we present anO (logn)-time andn(log lognl logn)-EREW-processor algorithm which constructs a tree with error less than 0.18, andO (k logn log^* n)-time andn-CREW-processor algorithm which produces a tree with error at most l/n ^k , and anO (k ² logn)-time andn ²-CREW-processor algorithm which produces a tree with error at most l/n ^k . As well, we describe two sequential algorithms, anO(kn)-time algorithm which produces a tree with error at most l/n ^k , and anO(kn)-time algorithm which produces a tree with error at most . The last two algorithms use different computation models.The first author's research was supported in part by NSERC Research Grant 3053. A part of this work was done while the second author was at the University of British Columbia.     

Routing on Meshes with Buses

We consider the problem of routing packets on an MIMD mesh-connected array of processors augmented with row and column buses. We give lower bounds and randomized algorithms for the problem of routing k-permutations (where each processor is the source and destination of exactly k packets) on a d-dimensional mesh with buses, which we call the (k,d)-routing problem. We give a general class of ``hard' permutations which we use to prove lower bounds for the (k,d)-routing problem, for all k,d≥ 1. For the (1,1)- and (1,2)-routing problems the worst-case permutations from this class are identical to ones published by other authors, as are the resulting lower bounds. However, we further show that the (1,d)-routing problem requires 0.72 ... n steps for d=3, 0.76 ... n steps for d=4, and slightly more than steps for all d≥ 5. We also obtain new lower bounds for the (k,d)-routing problem for k,d > 1, which improve on the bisection lower bound in some cases. These lower bounds hold for off-line routing as well. We develop efficient algorithms for the (k,1)-routing problem and for the problem of routing k-randomizations (where each processor has k packets initially and each packet is routed to a random destination) on the one-dimensional mesh and use them in a general (k,d)-routing algorithm which improves considerably on previous results. In particular, the routing time for the (1,d)-routing problem is bounded by steps with high probability (whp), whenever for some constant ε > 0, and the routing time for the (k,d)-routing problem is steps whp whenever for some constant ε > 0 and k≥ 3.6 ... d, matching the bisection lower bound. We then present a simple algorithm for the (2,2)-routing problem running in 1.39 ... n+o(n) steps whp. Finally, for the important special case of routing permutations on two-dimensional meshes with buses, the (1,2)-routing problem, we give a more sophisticated algorithm that runs in 0.78 ... n+o(n) steps whp. Received May 18, 1994; revised June 23, 1995.     

Common Intervals of Multiple Permutations

Given k permutations of n elements, a k-tuple of intervals of these permutations consisting of the same set of elements is called a common interval. We present an algorithm that finds in a family of k permutations of n elements all z common intervals in optimal O(kn+z) time and O(n) additional space. Additionally, we show how to adapt this algorithm to multichromosomal and circular permutations.     

Primality testing with fewer random bits

In the usual formulations of the Miller-Rabin and Solovay-Strassen primality testing algorithms for a numbern, the algorithm chooses candidatesx ₁,x ₂, ...,x _k uniformly and independently at random from _n , and tests if any is a witness to the compositeness ofn. For either algorithm, the probabilty that it errs is at most 2^–k .In this paper, we study the error probabilities of these algorithms when the candidates are instead chosen asx, x+1, ..., x+k–1, wherex is chosen uniformly at random from _n . We prove that fork=[1/2log₂ n], the error probability of the Miller-Rabin test is no more thann ^–1/2+o(1), which improves on the boundn ^–1/4+o(1) previously obtained by Bach. We prove similar bounds for the Solovay-Strassen test, but they are not quite as strong; in particular, we only obtain a bound ofn ^–1/2+o(1) if the number of distinct prime factors ofn iso(logn/loglogn).     

Line-segment intersection reporting in parallel

In this paper we give a parallel algorithm for line-segment intersection reporting in the plane. It runs in timeO(((n +k) logn log logn)/p) usingp processors on a concurrent-read-exclusive-write (CREW)-PRAM, wheren is the number of line segments,k is the number of intersections, andp n +k.This work was supported by the DFG, SFB 124, TP B2, VLSI Entwurfsmethoden und Parallelität.     

Randomized geometric algorithms and pseudorandom generators

It is shown that the bounds on the expected running times of most of the randomized incremental algorithms in computational geometry do not change by more than a constant factor when they are made pseudorandom using a very simple scheme. This reduces the number of random bits used by these algorithms from (nlogn) toO(logn).This research was supported by Packard fellowship.     

Optimal per-edge processing times in the semi-streaming model

We present semi-streaming algorithms for basic graph problems that have optimal per-edge processing times and therefore surpass all previous semi-streaming algorithms for these tasks. The semi-streaming model, which is appropriate when dealing with massive graphs, forbids random access to the input and restricts the memory to bits.Particularly, the formerly best per-edge processing times for finding the connected components and a bipartition are O(α(n)), for determining k-vertex and k-edge connectivity O(k²n) and O(n⋅logn) respectively for any constant k and for computing a minimum spanning forest O(logn). All these time bounds we reduce to O(1).Every presented algorithm determines a solution asymptotically as fast as the best corresponding algorithm up to date in the classical RAM model, which therefore cannot convert the advantage of unlimited memory and random access into superior computing times for these problems.     

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.     

Retrieval of scattered information by EREW,CREW, and CRCW PRAMs

Thek-compaction problem arises whenk out ofn cells in an array are non-empty and the contents of these cells must be moved to the firstk locations in the array. Parallel algorithms fork-compaction have obvious applications in processor allocation and load balancing;k-compaction is also an important subroutine in many recently developed oped parallel algorithms. We show that any EREW PRAM that solves thek-compaction problem requires time, even if the number of processors is arbitrarily large andk=2. On the CREW PRAM, we show that everyn-processor algorithm fork-compaction problem requires (log logn) time, even ifk=2. Finally, we show thatO(logk) time can be achieved on the ROBUST PRAM, a very weak CRCW PRAM model.     

An optimal algorithm for shortest paths on weighted interval and circular-arc graphs,with applications

We give the first linear-time algorithm for computing single-source shortest paths in a weighted interval or circular-arc graph, when we are given the model of that graph, i.e., the actual weighted intervals or circular-arcsand the sorted list of the interval endpoints. Our algorithm solves this problem optimally inO(n) time, wheren is the number of intervals or circular-arcs in a graph. An immediate consequence of our result is anO(qn + n logn)-time algorithm for the minimum-weight circle-cover problem, whereq is the minimum number of arcs crossing any point on the circle; then logn term in this time complexity is from a preprocessing sorting step when the sorted list of endpoints is not given as part of the input. The previously best time bounds were0(n logn) for this shortest paths problem, andO(qn logn) for the minimum-weight circle-cover problem. Thus we improve the bounds of both problems. More importantly, the techniques we give hold the promise of achieving similar (logn)-factor improvements in other problems on such graphs.The research of M. J. Atallah was supported in part by the Leonardo Fibonacci Institute, Trento, Italy, by the Air Force Office of Scientific Research under Contract AFOSR-90-0107, and by the National Science Foundation under Grant CCR-9202807. D. Z. Chen's research was supported in part by the Leonardo Fibonacci Institute, Trento, Italy. The research of D. T. Lee was supported in part by the Leonardo Fibonacci Institute, Trento, Italy, by the National Science Foundation, and the Office of Naval Research under Grants CCR-8901815, CCR-9309743, and N00014-93-1-0272.     

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.     

Optimal parallel algorithm for findingst-ambitus of a planar biconnected graph

A cycleC passing through two specific verticess andt of a biconnected graph is said to be anst-ambitus if its bridges do not interlace in some special way. We present algorithms forst-ambitus for planar biconnected graphs, which are much simpler than the one known for general graphs [MT]. Our algorithm runs inO(n) time on a sequential machine and (logn) parallel time usingO(n/logn) processors on an EREW PRAM.     

Parallel algorithms for some functions of two convex polygons

Let P andQ be two convex,n-vertex polygons. We consider the problem of computing, in parallel, some functions ofP andQ whenP andQ are disjoint. The model of parallel computation we consider is the CREW-PRAM, i.e., it is the synchronous shared-memory model where concurrent reads are allowed but no two processors can simultaneously attempt to write in the same memory location (even if they are trying to write the same thing). We show that a CREW-PRAM havingn ^1/k processors can compute the following functions in O(k¹⁺) time: (i) the common tangents betweenP andQ, and (ii) the distance betweenP andQ (and hence a straight line separating them). The positive constant can be made arbitrarily close to zero. Even with a linear number of processors, it was not previously known how to achieve constant time performance for computing these functions. The algorithm for problem (ii) is easily modified to detect the case of zero distance as well.This research was supported by the Office of Naval Research under Grants N00014-84-K-0502 and N00014-86-K-0689, and the National Science Foundation under Grant DCR-8451393, with matching funds from AT&T.     

A deterministicO(k 3)-competitivek-server algorithm for the circle

Suppose thatk mobile servers are located on a circle. Repeatedly, a request at a pointx on the circle appears. To serve this request one of the servers has to be moved tox. The cost of moving a server tox is the distance on the circle between the server's previous location andx. The decision which server to move has to be doneon-line; that is, without the knowledge of future requests. We give a deterministic on-line algorithm for making these decisions. Our algorithm isO(k ³)-competitive: for any sequence of requests, the cost incurred by our algorithm in serving this sequence is bounded (up to an additive constant) byO(k ³) times the cost of serving this sequence using the bestoff-line algorithm; i.e., an algorithm that hasa priori knowledge of the whole sequence. Our algorithm is the best deterministic constructive algorithm fork>2.     

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 algorithm for merging meaps

Summary We present an algorithm to merge priority queues organized as heaps. The worst case number of comparisons required to merge two heaps of sizes k and n is O(log(n)*log(k)). The algorithm requires O(k) +log(n)*log (k)) data movements if heaps are implemented using arrays and O(log(n)*log(k)) for a pointer-based implementation. Previous algorithms require either O(n+k) data movements and comparisons, or O(k*log(log(n+k))) comparisons and O(k*log(n+k)) data movements. The algorithm presented in this paper improves on the previous algorithms for the case when k>log(n).This work was done while the authors were at McGill University, Montréal, Canada     

Shorter strings containing all k-element permutations

We consider the problem of finding short strings that contain all permutations of order k over an alphabet of size n, with k?n. We show constructively that k(n−2)+3 is an upper bound on the length of shortest such strings, for n?k?10. Consequently, for n?10, the shortest strings that contain all permutations of order n have length at most n²−2n+3. These two new upper bounds improve with one unit the previous known upper bounds.