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
Abstract. 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...
A Communication Complexity Proof That Symmetric Functions Have Logarithmic Depth (2007)
Gerth Stlting Brodal, Thore Husfeldt
. We present a direct protocol with logarithmic communication that finds an element in the symmetric di#erence of two sets of di#erent size. This yields a simple proof that symmetric functions have...
ftp ftp.brics.aau.dk (cd pub/BRICS) Fast Meldable Priority Queues (2007)
Gerth Stlting Brodal, Gerth Stlting Brodal
is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent publications in the BRICS Report Series. Copies...
Gerth Stlting Brodal, Riko Jacob
Time-dependent networks as models to achieve
Lars Arge, Gerth Stlting Brodal, Laura Toma
Recently external memory graph algorithms have received considerable attention because massive graphs arise naturally in many applications involving massive data sets. Even though a large number of...
Web www.itu.dk Optimal Static Range Reporting in One Dimension (2007)
Stephen Alstrup, Stephen Alstrup, Gerth Stlting Brodal, Gerth Stlting Brodal, Gerth Stlting Brodal, Theis Rauhe, ...
All rights reserved. Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy. ISSN 1600--6100
Web www.it-c.dk Time and Space Efficient Multi-Method Dispatching (2007)
Stephen Alstrup, Stephen Alstrup, Gerth Stlting Brodal, Gerth Stlting Brodal, Gerth Stlting Brodal, Inge Li Grtz, ...
All rights reserved. Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy. ISSN 1600--6100 ISBN...
Web www.itu.dk Optimal Static Range Reporting in One Dimension (2007)
Gerth S. Brodal, Gerth S. Brodal, Stephen Alstrup, Stephen Alstrup, Gerth Stlting Brodal, Theis Rauhe, ...
All rights reserved. Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy. ISSN 1600--6100
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
Abstract 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...
Speeding up neighbour-joining tree construction (2003)
Gerth Stlting Brodal, Rolf Fagerberg, Thomas Mailund, 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 (2002)
Gerth Stlting Brodal, Rolf Fagerberg, 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...
Cache oblivious search trees via binary trees of small height (2002)
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...
Computing the quartet distance between evolutionary trees in time O(n log n (2001)
Gerth Stlting Brodal, Rolf Fagerberg
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...
Computing the quartet distance between evolutionary trees in time O(n log n (2001)
Abstract 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...
The complexity of constructing evolutionary trees using experiments (2001)
Gerth Stlting Brodal, Rolf Fagerberg, 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...
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...
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...
Finding maximal quasiperiodicities in strings (2000)
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...
Pattern Matching in Dynamic Texts (2000)
Stephen Alstrup Gerth, 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 pairs with bounded gap (1999)
Gerth Stlting Brodal, Rune B. Lyngs, 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, 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...
Improved Bounds for Dictionary Look-up with One Error (1999)
Gerth Stølting Brodal, Gerth Stlting Brodal, Srinivasan Venkatesh, 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...
Finding Maximal Quasiperiodicities in Strings (1999)
Gerth Stø:lting Brodal, Gerth Stlting Brodal, Gerth Stlting Brodal
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)....
Pinotti, 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 O(n) for the size of any heap construction...
Pinotti, 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 O(n) for the size of any heap construction...
A parallel priority queue with constant time operations (1998)
Gerth S. Brodal, Jesper L. Traff, Gerth Stlting Brodal, Jesper Larsson Traff, Christos D. Zaroliagis, 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...
Worst-case efficient external-memory priority queues (1998)
Gerth Stlting Brodal, Jyrki Katajainen
Abstract. 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...
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...
Optimal purely functional priority queues (1996)
Gerth Stlting Brodal, Gerth Stlting Brodal, Chris Okasaki, Chris Okasaki
is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent publications in the BRICS Report Series. Copies...
Partially Persistent Data Structures of Bounded Degree with Constant Update Time (1996)
Gerth Stlting Brodal, Gerth Stlting Brodal
is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent publications in the BRICS Report Series. Copies...
The Complexity of Computing the k-ary Composition of a Binary Associative Operator (1996)
Gerth Stølting Brodal, Gerth Stlting Brodal, Sven Skyum, 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 k\Gamma1 k+1 n \Gamma O(k) operations. For...
The Randomized Complexity of Maintaining the Minimum (1996)
Jaikumar Radhakrishnan, Gerth Stlting Brodal, Gerth Stlting Brodal
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...