A union-find data structure maintains a collection of disjoint sets under the operations makeset, union, and find. Kaplan, Shafrir, and Tarjan [SODA 2002] designed data structures for an extension of the union-find problem in which items of the sets maintained may be deleted. The cost of a delete operation in their implementations is essentially the same as the cost of a find operation; namely, O (log n ) worst-case and O (α ⌈ M / N ⌉ ( n )) amortized, where n is the number of items in the set returned by the find operation, N is the total number of makeset operations performed, M is the total number of find operations performed, and α ⌈ M / N ⌉ ( n ) is a functional inverse of Ackermann’s function. They left open the question whether delete operations can be implemented more efficiently than find operations, for example, in o (log n ) worst-case time. We resolve this open problem by presenting a relatively simple modification of the classical union-find data structure that supports delete, as well as makeset and union operations, in constant worst-case time, while still supporting find operations in O (log n ) worst-case time and O (α ⌈ M/N⌉ ( n )) amortized time. Our analysis supplies, in particular, a very concise potential-based amortized analysis of the standard union-find data structure that yields an O (α ⌈ M / N ⌉ ( n )) amortized bound on the cost of find operations. All previous potential-based analyses yielded the weaker amortized bound of O (α ⌈ M / N ⌉ ( N )). Furthermore, our tighter analysis extends to one-path variants of the path compression technique such as path splitting .

We consider the following problem. Given a rooted tree T, label the nodes of T in the most compact way such that, given the labels of two nodes u and v, one can determine in constant time, by looking only at the labels, whether u is ancestor of v. The best known labeling scheme is rather straightforward and uses labels of length at most $2\log_2 n$ bits each, where n is the number of nodes in the tree. Our main result in this paper is a labeling scheme with maximum label length $\log_2 n + \Oh(\sqrt{\log n})$. Our motivation for studying this problem is enhancing the performance of web search engines. In the context of this application each indexed document is a tree, and the labels of all trees are maintained in main memory. Therefore even small improvements in the maximum label length are important.

We consider labeling schemes for trees, supporting various relationships between nodes at small distance. For instance, we show that given a tree T and an integer k we can assign labels to each node of T such that given the label of two nodes we can decide, from these two labels alone, if the distance between v and w is at most k and, if so, compute it. For trees with n nodes and $k\geq 2$, we give a lower bound on the maximum label length of $\log n + \Omega(\log \log n)$ bits, and for constant k, we give an upper bound of log n + O(log log n). Bounds for ancestor, sibling, connectivity, and bi- and triconnectivity labeling schemes are also presented.

We present a simple black box that takes a priority queue Q which supports find-min, insert, and delete in x-time at most t . Here x-time may be worst-case, expected, or amortized. The black-box transforms Q into a priority queue Q * that supports find-min in constant time, insert in constant x-time, and delete in x-time O ( t ). Moreover, if Q supports dec-key in constant time, then so does Q *.

We study the complexity of the dynamic partial sum problem in the cell-probe model. We give the model access to nondeterministic queries and prove that the problem remains hard. We give the model access to the right answer $\pm 1$ as an oracle and prove that the problem remains hard. This suggests which kind of information is hard to maintain. From these results, we derive a number of lower bounds for dynamic algorithms and data structures: We prove lower bounds for dynamic algorithms for existential range queries, reachability in directed graphs, planarity testing, planar point location, incremental parsing, and fundamental data structure problems like maintaining the majority of the prefixes of a string of bits. We prove a lower bound for reachability in grid graphs in terms of the graph's width. We characterize the complexity of maintaining the value of any symmetric function on the prefixes of a bit string.

We show that there exists a graph G with n /spl middot/ 2/sup O(log* n)/ nodes, where any forest with n nodes is a node-induced subgraph of G. Furthermore, the result implies the existence of a graph with n/sup k/2/sup O(log* n)/ nodes that contains all n-node graphs of fixed arboricity k as node-induced subgraphs. We provide a lower bound of /spl Omega/(n/sup k/) for the size of such a graph. The upper bound is obtained through a simple labeling scheme for parent queries in rooted trees.

Several papers describe linear time algorithms to preprocess a tree, such that one can answer subsequent nearest common ancestor queries in constant time. Here, we survey these algorithms and related results. A common idea used by all the algorithms for the problem is that a solution for complete binary trees is straightforward. Furthermore, for complete binary trees we can easily solve the problem in a distributed way by labeling the nodes of the tree such that from the labels of two nodes alone one can compute the label of their nearest common ancestor. Whether it is possible to distribute the data structure into short labels associated with the nodes is important for several applications such as routing. Therefore, related labeling problems have received a lot of attention recently.Previous optimal algorithms for nearest common ancestor queries work using some mapping from a general tree to a complete binary tree. However, it is not clear how to distribute the data structures obtained using these mappings. We conclude our survey with a new simple algorithm that labels the nodes of a rooted tree such that from the labels of two nodes alone one can compute in constant time the label of their nearest common ancestor. The labels assigned by our algorithm are of size $O(\log n)$ bits where $n$ is the number of nodes in the tree. The algorithm runs in $O(n)$ time.

We consider static one dimensional range searching problems. These problems are to build static data structures for an integer set S \subseteq U, where U = \{0,1,\dots,2^w-1\}, which support various queries for integer intervals of U. For the query of reporting all integers in S contained within a query interval, we present an optimal data structure with linear space cost and with query time linear in the number of integers reported. This result holds in the unit cost RAM model with word size w and a standard instruction set. We also present a linear space data structure for approximate range counting. A range counting query for an interval returns the number of integers in S contained within the interval. For any constant ε>0, our range counting data structure returns in constant time an approximate answer which is within a factor of at most 1+ε of the correct answer.

We present new general techniques for static orthogonal range searching problems in two and higher dimensions. For the general range reporting problem in R/sup 3/, we achieve query time O(log n+k) using space O(n log/sup 1+/spl epsiv// n), where n denotes the number of stored points and k the number of points to be reported. For the range reporting problem on an n/spl times/n grid, we achieve query time O(log log n+k) using space O(n log/sup /spl epsiv// n). For the two-dimensional semi-group range sum problem we achieve query time O(log n) using space O(n log n).

We study the interplay between worst-case and amortised time bounds for the classic Disjoint Set Union problem (Union-Find). We ask whether it is possible to achieve optimal worst-case and amortised bounds simultaneously. Furthermore we would like to allow a tradeoff between the worst-case time for a query and for an update. We answer this question by first providing lower bounds for the possible worst-case time tradeoffs, as well as lower bounds which show where in this tradeoff range optimal amortised time is achievable. We then give an algorithm which tightly matches both lower bounds simultaneously. The lower bounds are provided in the cell-probe model as well as in the algebraic real-number RAM, and the upper bounds hold for a RAM with logarithmic word size and a modest instruction set. Our lower bounds show that for worst-case query and update time tq and tu respectively, one must have tq = \\Omega (log n = log tu), and only for tq * ff(m; n) can this tradeoff be achieved simultaneously with the optimal amortised time of \\Theta (ff(m; n)). Our

Consider a rooted tree whose nodes can be in two states: marked or unmarked. The marked ancestor problem is to maintain a data structure with the following operations: mark(v) marks node v: unmark(v) removes any marks from node v; firstmarked(v) returns the first marked node on the path from v to the root. We show tight upper and lower bounds for the marked ancestor problem. The lower bounds are proved in the cell probe model, the algorithms run on a unit-cost RAM. As easy corollaries we prove (often optimal) lower bounds on a number of problems. These include planar range searching, including the existential or emptiness problem, priority search trees static tree union-find, and several problems from dynamic computational geometry, including segment intersection, interval maintenance, and ray shooting in the plane. Our upper bounds improve algorithms from various fields, including coloured ancestor problems and maintenance of balanced parentheses.

We study the fundamental problem of sorting in a sequential model of computation and in particular consider the time-space trade-off (product of time and space) for this problem. P. Beame (1991) has shown a lower bound of /spl Omega/(n/sup 2/) for this product leaving a gap of a logarithmic factor up to the previously best known upper bound of O(n/sup 2/ log n) due to G.N. Frederickson (1987). Since then, no progress has been made towards tightening this gap. The main contribution of this paper is a comparison based sorting algorithm which closes the gap by meeting the lower bound of Beame. The time-space product O(n/sup 2/) upper bound holds for the full range of space bounds between log n and n/log n. Hence in this range our algorithm is optimal for comparison based models as well as for the very powerful general models considered by Beame.