The Temporal Precedence Problem

In this paper we analyze the complexity of the Temporal Precedence Problem on pointer machines. The problem is to support efficiently two operations: insert and precedes. The operation insert (a) introduces a new element a , while precedes (a,b) returns true iff element a was temporally inserted before element b . We provide a solution to the problem with worst-case time complexity O( lg lg n) per operation, where n is the number of elements inserted. We also demonstrate that the problem has a lower bound of Ω( lg lg n) on pointer machines. Thus the proposed scheme is optimal on pointer machines. Received February 5, 1998; revised October 21, 1998.     

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.     

Two new methods for constructing double-ended priority queues from priority queues

We introduce two data-structural transformations to construct double-ended priority queues from priority queues. To apply our transformations the priority queues exploited must support the extraction of an unspecified element, in addition to the standard priority-queue operations. With the first transformation we obtain a double-ended priority queue which guarantees the worst-case cost of O(1) for find-min, find-max, insert, extract; and the worst-case cost of O(lg n) with at most lg n + O(1) element comparisons for delete. With the second transformation we get a meldable double-ended priority queue which guarantees the worst-case cost of O(1) for find-min, find-max, insert, extract; the worst-case cost of O(lg n) with at most lg n + O(lg lg n) element comparisons for delete; and the worst-case cost of O(min {lg m, lg n}) for meld. Here, m and n denote the number of elements stored in the data structures prior to the operation in question. The work of the authors was partially supported by the Danish Natural Science Research Council under contracts 21-02-0501 (project Practical data structures and algorithms) and 272-05-0272 (project Generic programming—algorithms and tools). A. Elmasry was supported by Alexander von Humboldt fellowship.     

Parallel Construction of (a, b)-Trees

We present an optimal parallel algorithm for the construction of (a, b)-trees-a generalization of 2-3 trees, 2-3-4 trees, and B-trees. We show the existence of a canonical form for (a, b)-trees, with a very regular structure, which allows us to obtain a scalable parallel algorithm for the construction of a minimum-height (a, b)-tree with N keys in O(N/p + log log N) time using p ≤ N/log log N processors on the EREW-PRAM model, and in O(N/p) time using p ≤ N processors on the CREW model. We show that the average memory utilization for the canonical form is at least 50% better than that for the worst-case and is also better than that for a random (a, b)-tree. A significant feature of the proposed parallel algorithm is that its time-complexity depends neither on a nor on b, and hence our general algorithm is superior to earlier algorithms for parallel construction of B-trees.     

A balanced search tree with O(1) worst-case update time

Summary In this paper a new data structure is described for performing member and neighbor queries in O(logn) time that allows for O(1) worst-case update time once the position of the inserted or deleted element is known. In this way previous solutions that achieved only O(1) amortized time or O(log^* n) worst-case time are improved. The method is based on a combinatorial result on the height of piles that are split after some fixed number of insertions. This combinatorial result is interesting in its own right and might have other applications as well.     

Two-tier relaxed heaps

We introduce a data structure which provides efficient heap operations with respect to the number of element comparisons performed. Let n denote the size of the heap being manipulated. Our data structure guarantees the worst-case cost of O(1) for finding the minimum, inserting an element, extracting an (unspecified) element, and replacing an element with a smaller element; and the worst-case cost of O(lg n) with at most lg n + 3 lg lg n + O(1) element comparisons for deleting an element. We thereby improve the comparison complexity of heap operations known for run-relaxed heaps and other worst-case efficient heaps. Furthermore, our data structure supports melding of two heaps of size m and n at the worst-case cost of O(min {lg m, lg n}). A preliminary version of this paper [8] was presented at the 17th International Symposium on Algorithms and Computation held in Kolkata in December 2006. Partially supported by the Danish Natural Science Research Council under contracts 21-02-0501 (project Practical data structures and algorithms) and 272-05-0272 (project Generic programming—algorithms and tools).     

Direct dominance of points

Several transitive relations of geometrical objects (like inclusion of intervals on a line or polygons in the plain), which are important in VLSI design applications, can be translated into the dominance relation a dominates b iff (a ≠ b and a _j ≧ b _j for j = 1,…d) of points a = (a ₁,...,a _d ),b = (b ₁,…b _d ) in R ^d by representing the objects as points in a suitable way. If only the transitive reduction (see [7]) of the given relation is required and not all the implications by transitivity, one can restrict oneself to the direct dominances in the corresponding point set N; here a dominates b directly means that a dominates b and there is no—with respect to dominance—intermediate c in N (see [5]). To estimate the advantage of this restriction, information about the numbers of dominant and directly dominant pairs in a set of n points is required, both numbers essentially depending upon how the points are distributed in R ^d . In this paper we assume the n points in question to be identically and independently distributed; then we can expect q·n·(n–1) dominance pairs. For a certain class of distributions including the uniform distribution we prove the theorem, that the expected number of direct dominance pairs is asymptotically equal to 1/(d?1)! · n1n ^{d ? 1}(n). Hence algorithms which compute only the direct dominances instead of all dominances are worth to be considered.     

Implementing Shared Memory on Mesh-Connected Computers and on the Fat-Tree

We present deterministic upper and lower bounds on the slowdown required to simulate an (n, m)-PRAM on a variety of networks. The upper bounds are based on a novel scheme that exploits the splitting and combining of messages. This scheme can be implemented on an n-node d-dimensional mesh (for constant d) and on an n-leaf pruned butterfly and attains the smallest worst-case slowdown to date for such interconnections, namely, O(n^1/d(log(m/n))^1-1/d) for the d-dimensional mesh (with constant d) and O( ) for the pruned butterfly. In fact, the simulation on the pruned butterfly is the first PRAM simulation scheme on an area-universal network. Finally, we prove restricted and unrestricted lower bounds on the slowdown of any deterministic PRAM simulation on an arbitrary network, formulated in terms of the bandwidth properties of the interconnection as expressed by its decomposition tree.     

Malign Distributions for Average Case Circuit Complexity

In contrast to machine models like Turing machines or random access machines, circuits are a static computational model. The internal information flow of a computation is fixed in advance, independent of the actual input. Therefore, size and depth are natural and simple measures for circuits and provide a worst-case analysis. We consider a new model in which an internal gate is evaluated as soon as its result has been determined by a partial assignment of its inputs. This way, a dynamic notion of delay is obtained which gives rise to an average case measure for the time complexity of circuits. In a previous paper we have obtained tight upper and lower bounds for the average case complexity of several basic Boolean functions. This paper examines the asymptotic average case complexity for the set of alln-ary Boolean functions. In contrast to worst case analysis a simple counting argument does not work. We prove that with respect to the uniform probability distribution almost all Boolean functions require at leastn−log n−log log nexpected time. On the other hand, there is a significantly large subset of functions that can be computed with a constant average delay. Finally, for an arbitrary Boolean function we compare its worst case and average case complexity. It is shown that for each function that requires circuit depthd, i.e. of worst-case complexityd, the expected time complexity will be at leastd−log n−log dwith respect to an explicitly defined probability distribution. In addition, a nontrivial upper bound on the complexity of such a distribution will be obtained.     

A better performance guarantee for approximate graph coloring

Approximate graph coloring takes as input a graph and returns a legal coloring which is not necessarily optimal. We improve the performance guarantee, or worst-case ratio between the number of colors used and the minimum number of colors possible, toO(n(log logn)³/(logn)³), anO(logn/log logn) factor better than the previous best-known result.The work of the first author was supported by Air Force Grant AFOSR-86-0078 and NSF PYI Grant 8657527-CCR. The work of the second author was supported by a National Science Foundation Graduate Fellowship.     

Simple Algorithms for the On-Line Multidimensional Dictionary and Related Problems

The on-line multidimensional dictionary problem consists of executing on-line any sequence of the following operations: INSERT(p) , DELETE(p) , and MEM-BER-SHIP(p) , where p is any (ordered) d -tuple (or string with d elements, or points in d -space where the dimensions have been ordered). We introduce a clean structure based on balanced binary search trees, which we call multidimensional balanced binary search trees, to represent the set of d -tuples. We present algorithms for each of the above operations that take O(d + log n) time, where n is the current number of d -tuples in the set, and each INSERT and DELETE operation requires no more than a constant number of rotations. Our structure requires dn words to represent the input, plus O(n) pointers and data indicating the first component where pairs of d -tuples differ. This information, which can be easily updated, enables us to test for MEMBERSHIP efficiently. Other operations that can be performed efficiently in our multidimensional balanced binary search trees are: print in lexicographic order (O(dn) time), find the (lexicographically) smallest or largest d -tuple (O( log n) time), and concatenation (O(d + log n) time). Finding the (lexicographically) k th smallest or largest d -tuple can also be implemented efficiently (O( log n) time), at the expense of adding an integer value at each node. Received June 13, 1997; revised September 3, 1998.     

Communication complexity towards lower bounds on circuit depth

Karchmer, Raz, and Wigderson (1995) discuss the circuit depth complexity of n-bit Boolean functions constructed by composing up to d = log n/log log n levels of k = log n-bit Boolean functions. Any such function is in AC¹ . They conjecture that circuit depth is additive under composition, which would imply that any (bounded fan-in) circuit for this problem requires depth. This would separate AC¹ from NC¹. They recommend using the communication game characterization of circuit depth. In order to develop techniques for using communication complexity to prove circuit depth lower bounds, they suggest an intermediate communication complexity problem which they call the Universal Composition Relation. We give an almost optimal lower bound of dk—O(d ²(k log k)^1/2) for this problem. In addition, we present a proof, directly in terms of communication complexity, that there is a function on k bits requiring circuit depth. Although this fact can be easily established using a counting argument, we hope that the ideas in our proof will be incorporated more easily into subsequent arguments which use communication complexity to prove circuit depth bounds. Received: July 30, 1999.     

Linear-Space Data Structures for Range Mode Query in Arrays

A mode of a multiset S is an element a∈S of maximum multiplicity; that is, a occurs at least as frequently as any other element in S. Given an array A[1:n] of n elements, we consider a basic problem: constructing a static data structure that efficiently answers range mode queries on A. Each query consists of an input pair of indices (i,j) for which a mode of A[i:j] must be returned. The best previous data structure with linear space, by Krizanc, Morin, and Smid (Proceedings of the International Symposium on Algorithms and Computation (ISAAC), pp. 517–526, 2003), requires \(\varTheta (\sqrt{n}\log\log n)\) query time in the worst case. We improve their result and present an O(n)-space data structure that supports range mode queries in \(O(\sqrt{n/\log n})\) worst-case time. In the external memory model, we give a linear-space data structure that requires \(O(\sqrt{n/B})\) I/Os per query, where B denotes the block size. Furthermore, we present strong evidence that a query time significantly below \(\sqrt{n}\) cannot be achieved by purely combinatorial techniques; we show that boolean matrix multiplication of two \(\sqrt{n} \times \sqrt{n}\) matrices reduces to n range mode queries in an array of size O(n). Additionally, we give linear-space data structures for the dynamic problem (queries and updates in near O(n ^3/4) time), for orthogonal range mode in d dimensions (queries in near O(n ^1?1/2d ) time) and for half-space range mode in d dimensions (queries in \(O(n^{1-1/d^{2}})\) time). Finally, we complement our dynamic data structure with a reduction from the multiphase problem, again supporting that we cannot hope for much more efficient data structures.     

Matching upper and lower bounds for simulations of several linear tapes on one multidimensional tape

We prove an O(t(n) ^d (t(n)) ^? / log t(n)) time bound for the sim-ulation of t(n) steps of a Turing machine using several one-dimensional work tapes on a Turing machine using one d-dimensional work tape, . We prove a matching lower bound which holds for the problem of recognizing languages on machines with a separate one-way input tape. Received: March 1995.     

Computing the subset partial order for dense families of sets

We give an algorithm to compute the subset partial order (called the subset graph) for a family F of sets containing k sets with N elements in total and domain size n. Our algorithm requires O(nk²/logk) time and space on a Pointer Machine. When F is dense, i.e. N=Θ(nk), the algorithm requires O(N²/log²N) time and space. We give a construction for a dense family whose subset graph is of size Θ(N²/log²N), indicating the optimality of our algorithm for dense families. The subset graph can be dynamically maintained when F undergoes set insertions and deletions in O(nk/logk) time per update (that is sub-linear in N for the case of dense families). If we assume words of b?k bits, allow bits to be packed in words, and use bitwise operations, the above running time and space requirements can be reduced by a factor of blog(k/b+1)/logk and b²log(k/b+1)/logk respectively.     

A sweepline algorithm for Euclidean Voronoi diagram of circles

Presented in this paper is a sweepline algorithm to compute the Voronoi diagram of a set of circles in a two-dimensional Euclidean space. The radii of the circles are non-negative and not necessarily equal. It is allowed that circles intersect each other, and a circle contains others.The proposed algorithm constructs the correct Voronoi diagram as a sweepline moves on the plane from top to bottom. While moving on the plane, the sweepline stops only at certain event points where the topology changes occur for the Voronoi diagram being constructed.The worst-case time complexity of the proposed algorithm is O((n+m)log n), where n is the number of input circles, and m is the number of intersection points among circles. As m can be O(n²), the presented algorithm is optimal with O(n² log n) worst-case time complexity.     

Sub-Constant Error Probabilistically Checkable Proof of Almost-Linear Size

We show a construction of a PCP with both sub-constant error and almost-linear size. Specifically, for some constant 0 < α < 1, we construct a PCP verifier for checking satisfiability of Boolean formulas that on input of size n uses log n+O((log n)^1-a)\log\, n+O((\log\, n)^{1-\alpha}) random bits to make 7 queries to a proof of size n·2^{O((log n)1-a)}n·2^{O((\log\, n)^{1-\alpha})}, where each query is answered by O((log n)^1-a)O((\log\, n)^{1-\alpha}) bit long string, and the verifier has perfect completeness and error 2^{-W((log n)a)}2^{-\Omega((\log\, n)^{\alpha})}.     

Lower Bounds for Fully Dynamic Connectivity Problems in Graphs

We prove lower bounds on the complexity of maintaining fully dynamic k -edge or k -vertex connectivity in plane graphs and in (k-1) -vertex connected graphs. We show an amortized lower bound of (log n / {k (log log n} + log b)) per edge insertion, deletion, or query operation in the cell probe model, where b is the word size of the machine and n is the number of vertices in G . We also show an amortized lower bound of (log n /(log log n + log b)) per operation for fully dynamic planarity testing in embedded graphs. These are the first lower bounds for fully dynamic connectivity problems. Received January 1995; revised February 1997.     

An O(n log n) Average Time Algorithm for Computing the Shortest Network under a Given Topology

In 1992 F. K. Hwang and J. F. Weng published an O(n ² ) time algorithm for computing the shortest network under a given full Steiner topology interconnecting n fixed points in the Euclidean plane. The Hwang—Weng algorithm can be used to improve substantially existing algorithms for the Steiner minimum tree problem because it reduces the number of different Steiner topologies to be considered dramatically. In this paper we present an improved Hwang—Weng algorithm. While the worst-case time complexity of our algorithm is still O(n ² ) , its average time complexity over all the full Steiner topologies interconnecting n fixed points is O (n log n ). Received August 24, 1996; revised February 10, 1997.     

Eclecticism shrinks even small worlds

We consider small world graphs as defined by Kleinberg (2000), i.e., graphs obtained from a d-dimensional mesh by adding links chosen at random according to the d-harmonic distribution. In these graphs, greedy routing performs in O(log ² n) expected number of steps. We introduce indirect-greedy routing. We show that giving O(log ² n) bits of topological awareness per node enables indirect-greedy routing to perform in O(log ^1+1/d n) expected number of steps in d-dimensional augmented meshes. We also show that, independently of the amount of topological awareness given to the nodes, indirect-greedy routing performs in Ω(log ^1+1/d n) expected number of steps. In particular, augmenting the topological awareness above this optimum of O(log ² n) bits would drastically decrease the performance of indirect-greedy routing. Our model demonstrates that the efficiency of indirect-greedy routing is sensitive to the “world’s dimension,” in the sense that high dimensional worlds enjoy faster greedy routing than low dimensional ones. This could not be observed in Kleinberg’s routing. In addition to bringing new light to Milgram’s experiment, our protocol presents several desirable properties. In particular, it is totally oblivious, i.e., there is no header modification along the path from the source to the target, and the routing decision depends only on the target, and on information stored locally at each node. A preliminary version of this paper appeared in the proceedings of the 23rd ACM Symposium on Principles of Distributed Computing (PODC), St. Johns, Newfoundland, Canada, July 25–28, 2004.