Gerth Stlting Brodal

Dynamic Planar Convex Hull (2003)

In this paper, we present lower bounds for permuting and sorting in the cache-oblivious model. We prove that (1) I/O optimal cache-oblivious comparison based sorting is not possible without a tall...

Optimal Finger Search Trees in the Pointer (2003)

In this paper we determine the amortized computational complexity of the dynamic convex hull problem in the planar case. We present a data structure that maintains a finite set of n points in the...

Gerth Stlting Brodal, George Lagogiannis, Christos Makris, Athanasios Tsakalidis, Kostas Tsichlas

We develop a new finger search tree with worst case constant update time in the Pointer Machine (PM) model of computation. This was a major problem in the field of Data Structures and was...

Solving the String Statistics Problem (2002)

Gerth Stlting Brodal, Rune B. Lyngs Anna, Christian N. S. Pedersen

The string statistics problem consists of preprocessing a string of length n such that given a query pattern of length m, the maximum number of non-overlapping occurrences of the query pattern in the...

Lower Bounds for External Memory Dictionaries (2002)

Funnel Heap - A Cache Oblivious Priority Queue Gerth Stlting Brodal (2002)

We study trade-offs between the update time and the query time for comparison based external memory dictionaries. The main contributions of this paper are two lower bound trade-offs between the I/O...

Time-Dependent Networks as Models to Achieve (2002)

The cache oblivious model of computation is a two-level memory model with the assumption that the parameters of the model are unknown to the algorithms. A consequence of this assumption is that an...

Cache Oblivious Search Trees via Binary Trees of Small Height (2002)

We consider ecient algorithms for exact time-table queries, i.e. algorithms that nd optimal itineraries. We propose to use time-dependent networks as a model and show advantages of this approach over...

Gerth Stlting Brodal, Rolf Fagerberg Riko Jacob

We propose a version of cache oblivious search trees which is simpler than the previous proposal of Bender, Demaine and Farach-Colton and has the same complexity bounds. In particular, our data...

Cache Oblivious Search Trees via Binary Trees of Small Height (2002)

Gerth Stlting Brodal, Rolf Fagerberg, Riko Jacob

We propose a version of cache oblivious search trees which is simpler than the previous proposal of Bender, Demaine and Farach-Colton and has the same complexity bounds. In particular, our data...

Dynamic Planar Convex Hull (2002)

Funnel Heap - A Cache Oblivious Priority Queue (2002)

In this paper we determine the computational complexity of the dynamic convex hull problem in the planar case. We present a data structure that maintains a finite set of n points in the plane under...

Cache Oblivious Distribution Sweeping (2002)

The cache oblivious model of computation is a two-level memory model with the assumption that the parameters of the model are unknown to the algorithms. A consequence of this assumption is that an...

Cache Oblivious Distribution Sweeping (2002)

We adapt the distribution sweeping method to the cache oblivious model. Distribution sweeping is the name used for a general approach for divide-and-conquer algorithms where the combination of solved...

Solving the String Statistics Problem (2002)

We adapt the distribution sweeping method to the cache oblivious model. Distribution sweeping is the name used for a general approach for divide-and-conquer algorithms where the combination of solved...

Gerth Stlting Brodal, Rune B. Lyngs, Anna Ostlin, Christian N. S. Pedersen

The string statistics problem consists of preprocessing a string of length n such that given a query pattern of length m, the maximum number of non-overlapping occurrences of the query pattern in the...

Time and Space Efficient Multi-Method Dispatching (2001)

Copyright C, Stephen Alstrup, Gerth Stlting Brodal, Inge Li Grtz, Theis Rauhe

The dispatching problem for object oriented languages is the problem of determining the most specialized method to invoke for calls at run-time. This can be a critical component of execution...

Computing the Quartet Distance Between Evolutionary Trees in Time (2001)

Gerth Stlting Brodal, Rolf Fagerberg, Christian N. S. Pedersen

Evolutionary trees describing the relationship for a set of species are central in evolutionary biology, and quantifying di#erences between evolutionary trees is an important task. One previously...

Time-Dependent Networks as Models to Achieve Fast Exact Time-Table Queries (2001)

The Complexity of Constructing Evolutionary Trees Using Experiments (2001)

We consider ecient algorithms for exact time-table queries, i.e. algorithms that find optimal itineraries. We propose to use time-dependent networks as a model and show advantages of this approach...

Gerth Stlting Brodal, Rolf Fagerberg, Christian N. S. Pedersen, Anna Stlin

We present tight upper and lower bounds for the problem of constructing evolutionary trees in the experiment model. We describe an algorithm which constructs an evolutionary tree of n species in time...

Computing the Quartet Distance Between Evolutionary Trees in Time (2001)

Gerth Stlting Brodal, Rolf Fagerberg, Christian N. S. Pedersen

Evolutionary trees describing the relationship for a set of species are central in evolutionary biology. Comparing evolutionary trees to quantify dierences arising when estimating trees using dierent...

Optimal Static Range Reporting in One Dimension (2001)

The Complexity of Constructing Evolutionary Trees Using Experiments (2001)

We consider static one dimensional range searching problems. These problems are to build static data structures for an integer set S

Gerth Stlting Brodal, Rolf Fagerberg, Christian N. S. Pedersen

We present tight upper and lower bounds for the problem of constructing evolutionary trees in the experiment model. We describe an algorithm which constructs an evolutionary tree of n species in time...

New Data Structures for Orthogonal Range Searching (2001)

Optimal Static Range Reporting in One Dimension (2000)

We present new general techniques for static orthogonal range searching problems in two and higher dimensions. For the general range reporting problem in R 3 , we achieve query time O(log n+ k) using...

Comparator Networks for Binary Heap Construction (2000)

We consider static one dimensional range searching problems. These problems are to build static data structures for an integer set S U , where U = f0; 1; : : : ; 2 w 1g, which support various queries...

Gerth Stlting Brodal, M. Cristina Pinotti

Comparator networks for constructing binary heaps of size n are presented which have size O(n log log n) and depth O(log n). A lower bound of n log log n O(n) for the size of any heap construction...

Optimal Static Range Reporting in One Dimension (2000)

Gerth S. Brodal, Stephen Alstrup, Gerth Stlting Brodal, Theis Rauhe

We consider static one dimensional range searching problems. These problems are to build static data structures for an integer set S U , where U = f0; 1; : : : ; 2 w 1g, which support various queries...

Amortized Analysis of ...-Trees (2000)

New Data Structures for Orthogonal Range Searching (2000)

f an (a; b)-tree. Theorem 1 An (a; b)-tree with n leaves has height between l log n log b m and j (log n) 1 log a k + 1. Proof. For a tree with n leaves and height h we have by Denition 1 that 2 a h...

Pattern Matching in Dynamic Texts (2000)

We present new general techniques for static orthogonal range searching problems in two and higher dimensions. For the general range reporting problem in R^3, we achieve query time O(log n + k) using...

Finding Maximal Quasiperiodicities in Strings (2000)

Pattern matching is the problem of finding all occurrences of a pattern in a text. In a dynamic setting the problem is to support pattern matching in a text which can be manipulated on-line, i.e.,...

Gerth Stlting Brodal, Christian N. S. Pedersen

Apostolico and Ehrenfeucht defined the notion of a maximal quasiperiodic substring and gave an algorithm that finds all maximal quasiperiodic substrings in a string of length n in time O(n log 2 n)....

Finding Maximal Quasiperiodicities in Strings (2000)

Gerth Stlting Brodal, Christian N. S. Pedersen

Apostolico and Ehrenfeucht dened the notion of a maximal quasiperiodic substring and gave an algorithm that nds all maximal quasiperiodic substrings in a string of length n in time O(n log 2 n). In...

Improved Bounds for Dictionary Look-up with One Error (2000)

Gerth Stlting Brodal, S. Venkatesh

Given a dictionary S of n binary strings each of length m, we consider the problem of designing a data structure for S that supports d-queries; given a binary query string q of length m, a d-query...

Dynamic Planar Convex Hull with Optimal Query Time and O(log n log log n) Update Time (2000)

Comparator Networks for Binary Heap Construction (2000)

The dynamic maintenance of the convex hull of a set of points in the plane is one of the most important problems in computational geometry. We present a data structure supporting point insertions in...

Gerth Stlting Brodal, M. Cristina Pinotti

Comparator networks for constructing binary heaps of size n are presented which have size O(n log log n) and depth O(log n). A lower bound of n log log n O(n) for the size of any heap construction...

Finding Maximal Quasiperiodicities in Strings (2000)

Gerth Stlting Brodal, Christian N. S. Pedersen

. Apostolico and Ehrenfeucht dened the notion of a maximal quasiperiodic substring and gave an algorithm that nds all maximal quasiperiodic substrings in a string of length n in time O(n log 2 n). In...

Improved Bounds for Dictionary Look-up with One Error (2000)

Gerth Stlting Brodal, Srinivasan Venkatesh, Gerth Stlting, Brodal Srinivasan Venkatesh

Given a dictionary S of n binary strings each of length m, we consider the problem of designing a data structure for S that supports d-queries; given a binary query string q of length m, a d-query...

Pattern Matching in Dynamic Texts (1999)

Finding Maximal Quasiperiodicities in Strings (1999)

Pattern matching is the problem of nding all occurrences of a pattern in a text. In a dynamic setting the problem is to support pattern matching in a text which can be manipulated on-line, i.e., the...

Gerth Stlting Brodal, Christian N. S. Pedersen

Apostolico and Ehrenfeucht defined the notion of a maximal quasiperiodic substring and gave an algorithm that finds all maximal quasiperiodic substrings in a string of length n in time O(n log 2 n)....

Finding Maximal Pairs with Bounded Gap (1999)

Gerth Stlting Brodal, Rune B. Lyngs, Copyright C, Gerth Stlting, Brodal Rune, B. Lyngs, ...

A pair in a string is the occurrence of the same substring twice. A pair is maximal if the two occurrences of the substring cannot be extended to the left and right without making them different. The...

Finding Maximal Pairs with Bounded Gap (1999)

Gerth Stlting Brodal, Rune B. Lyngs, Christian N. S. Pedersen, Jens Stoye

A pair in a string is the occurrence of the same substring twice. A pair is maximal if the two occurrences of the substring cannot be extended to the left and right without making them dierent. The...

Finding Maximal Pairs With Bounded Gap (1999)

Gerth Stlting Brodal, Rune B. Lyngs, Christian N. S. Pedersen, Jens Stoye

A pair in a string is the occurrence of the same substring twice. A pair is maximal if the two occurrences of the substring cannot be extended to the left and right without making them dierent. The...

Dynamic Representations of Sparse Graphs (1999)

Finding Maximal Pairs With Bounded Gap (1999)

We present a linear space data structure for maintaining graphs with bounded arboricity - a large class of sparse graphs containing e.g. planar graphs and graphs of bounded treewidth - under edge...

Gerth Stlting Brodal, Rune B. Lyngs, Christian N. S. Pedersen, Jens Stoye

A pair in a string is the occurrence of the same substring twice. A pair is maximal if the two occurrences of the substring cannot be extended to the left and right without making them dierent. The...

Priority Queues on Parallel Machines (1999)

Worst-Case Efficient External-Memory Priority Queues (1998)

We present time and work optimal priority queues for the CREW PRAM, supporting FindMin in constant time with one processor and MakeQueue, Insert, Meld, FindMin, ExtractMin, Delete and DecreaseKey in...

Comparator Networks for Binary Heap Construction (1998)

. A priority queue Q is a data structure that maintains a collection of elements, each element having an associated priority drawn from a totally ordered universe, under the operations Insert, which...

Gerth Stlting Brodal, M. Cristina Pinotti

Comparator networks for constructing binary heaps of size n are presented which have size O(n log log n) and depth O(log n). A lower bound of n log log n Gamma O(n) for the size of any heap...

Finger Search Trees with Constant Insertion Time (1997)

A Parallel Priority Queue with Constant Time Operations (1997)

We consider the problem of implementing finger search trees on the pointer machine, i.e., how to maintain a sorted list such that searching for an element x, starting the search at any arbitrary...

Gerth Stlting Brodal, Jesper Larsson Traff, Christos D. Zaroliagis

We present a parallel priority queue that supports the following operations in constant time: parallel insertion of a sequence of elements ordered according to key, parallel decrease key for a...

A Parallel Priority Queue with Constant Time Operations (1997)

Gerth S. Brodal, Jesper L. Traff, Gerth Stlting Brodal, Jesper Larsson Traff, Christos D. Zaroliagis

We present a parallel priority queue that supports the following operations in constant time: parallel insertion of a sequence of elements ordered according to key, parallel decrease key for a...

Predecessor Queries in Dynamic Integer Sets (1997)

The Randomized Complexity Of Maintaining The Minimum (1997)

. We consider the problem of maintaining a set of n integers in the range 0::2 w Gamma 1 under the operations of insertion, deletion, predecessor queries, minimum queries and maximum queries on a...

A Parallel Priority Data Structure with Applications (1997)

. The complexity of maintaining a set under the operations Insert, Delete and FindMin is considered. In the comparison model it is shown that any randomized algorithm with expected amortized cost t...

Gerth Stlting Brodal, Jesper Larsson, Tr Christos, D. Zaroliagis

We present a parallel priority data structure that improves the running time of certain algorithms for problems that lack a fast and work-efficient parallel solution. As a main application, we give a...

The Complexity of Computing the k-ary Composition of a Binary Associative Operator (1996)

Gerth Stlting Brodal, Sven Skyum

We show that the problem of computing all contiguous k-ary compositions of a sequence of n values under an associative and commutative operator requires 3 kGamma1 k+1 n Gamma O(k) operations. For the...

Predecessor Queries in Dynamic Integer Sets (1996)