Arrow Research search

Author name cluster

Theis Rauhe

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

12 papers
2 author rows

Possible papers

12

I&C Journal 2004 Journal Article

Dynamic nested brackets

  • Stephen Alstrup
  • Thore Husfeldt
  • Theis Rauhe

We consider the problem of maintaining a string of n brackets `('or `)' under the operation reverse(i) that changes the ith bracket from `(' to `)' or vice versa, and returns `yes' if and only if the resulting string is properly balanced. We show that this problem can be solved on the RAM in time O(logn/loglogn) per operation using linear space and preprocessing. Moreover, we show that this is optimal in the sense that every data structure supporting reverse (no matter its space and preprocessing complexity) needs time Ω(logn/loglogn) per operation in the cell probe model.

Details DOI

FOCS Conference 2002 Conference Paper

Small Induced-Universal Graphs and Compact Implicit Graph Representations

  • Stephen Alstrup
  • Theis Rauhe

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.

Details

STOC Conference 2001 Conference Paper

Optimal static range reporting in one dimension

  • Stephen Alstrup
  • Gerth Stølting Brodal
  • Theis Rauhe

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.

Details

FOCS Conference 2000 Conference Paper

New Data Structures for Orthogonal Range Searching

  • Stephen Alstrup
  • Gerth Stølting Brodal
  • Theis Rauhe

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).

Details

FOCS Conference 1998 Conference Paper

Marked Ancestor Problems

  • Stephen Alstrup
  • Thore Husfeldt
  • Theis Rauhe

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.

Details

FOCS Conference 1998 Conference Paper

Optimal Time-Space Trade-Offs for Sorting

  • Jakob Pagter
  • Theis Rauhe

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.

Details
v2026.09.13