The Cost of Cache-Oblivious Searching (2004)
Michael A. Bender, Gerth Stlting Brodal, Rolf Fagerberg, Dongdong Ge, Simai He, Haodong Hu, ...
Tight bounds on the cost of cache-oblivious searching are proved. It is shown that no cache-oblivious search structure can guarantee that a search performs fewer than lg e log B N block transfers...
Alcom-FT Technical Report Series (2004)
Gerth Stlting Brodal, Rolf Fagerberg, Thomas Mailund, Christian N. S. Pedersen, Derek Phillips
A widely used method for constructing phylogenetic trees is the neighbour-joining method of Saitou and Nei. We develope heuristics for speeding up the neighbour-joining method which generate the same...
Computing Refined Buneman Trees in Cubic Time (2003)
Gerth Stlting Brodal, Rolf Fagerberg, Ostlin Christian N. S. Pedersen, S. Srinivasa Rao
Reconstructing the evolutionary tree for a set of n species based on pairwise distances between the species is a fundamental problem in bioinformatics. Neighbor joining is a popular distance based...
Alcom-FT Technical Report Series (2003)
Gerth Stlting Brodal, Erik D. Demaine, J. Ian Munro
We propose several modifications to the binary buddy system for managing dynamic allocation of memory blocks whose sizes are powers of two. The standard buddy system allocates and deallocates blocks...
On the Limits of Cache-Obliviousness (2003)
Gerth Stlting Brodal, Rolf Fagerberg
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...
Dynamic Planar Convex Hull (2003)
Gerth Stlting Brodal, Riko Jacob
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...
Optimal Finger Search Trees in the Pointer (2003)
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)
Gerth Stlting Brodal, Rolf Fagerberg
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...
Funnel Heap - A Cache Oblivious Priority Queue Gerth Stlting Brodal (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...
Time-Dependent Networks as Models to Achieve (2002)
Gerth Stlting Brodal, Riko Jacob
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...
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...
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)
Gerth Stlting Brodal, Riko Jacob
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...
Funnel Heap - A Cache Oblivious Priority Queue (2002)
Gerth Stlting Brodal, Rolf Fagerberg
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)
Gerth Stlting Brodal, Rolf Fagerberg
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...
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)
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)
Gerth Stlting Brodal, Riko Jacob
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...
The Complexity of Constructing Evolutionary Trees Using Experiments (2001)
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)
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
The Complexity of Constructing Evolutionary Trees Using Experiments (2001)
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)
Stephen Alstrup, Gerth Stlting 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 3 , we achieve query time O(log n+ k) using...
Optimal Static Range Reporting in One Dimension (2000)
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...
Comparator Networks for Binary Heap Construction (2000)
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)
Gerth Stlting Brodal, Rolf Fagerberg
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...
New Data Structures for Orthogonal Range Searching (2000)
Stephen Alstrup, Gerth Stlting 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^3, we achieve query time O(log n + k) using...
Pattern Matching in Dynamic Texts (2000)
Stephen Alstrup, Gerth Stlting Brodal, Theis Rauhe
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.,...
Finding Maximal Quasiperiodicities in Strings (2000)
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)
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...
Comparator Networks for Binary Heap Construction (2000)
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)
Stephen Alstrup, Gerth Stlting Brodal, Theis Rauhe
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...
Finding Maximal Quasiperiodicities in Strings (1999)
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)
Gerth Stlting Brodal, Rolf Fagerberg
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...
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...
Priority Queues on Parallel Machines (1999)
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...
Worst-Case Efficient External-Memory Priority Queues (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...
Comparator Networks for Binary Heap Construction (1998)
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)
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...
A Parallel Priority Queue with Constant Time Operations (1997)
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)
. 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...
The Randomized Complexity Of Maintaining The Minimum (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...
A Parallel Priority Data Structure with Applications (1997)
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)
. 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...
The Randomized Complexity of Maintaining the Minimum (1996)
Shiva Chaudhuri, Gerth Stlting Brodal, Jaikumar Radhakrishnan
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...
The Randomized Complexity of Maintaining the Minimum (1996)
Gerth Stlting Brodal, Shiva Chaudhuri, Jaikumar Radhakrishnan
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...