Recrafting the Neighbor-Joining Mehtod (2009)
Gerth Stølting Brodal, Rolf Fagerberg, Thomas Mailund, Derek Phillips
Abstract The neighbor-joining method by Saitou and Nei is a widely used method for constructing phylogenetic trees. The formulation of the method gives rise to a canonical Θ(n 3) algorithm upon...
[DB03] Datamation Benchmark. Sort Benchmark Home Page, hosted by Microsoft. (2008)
Acv Rajiv Wickremesinghe, Lars Arge, Jeff Chase, S. Vitter, ...
[AV88] ALOK AGGARWAL AND JEFFERY S. VITTER. The input/output complexity of sorting and related problems. Communications of the ACM, 1988.
Abstract On the Adaptiveness of Quicksort (2008)
Gerth Stølting Brodal, Rolf Fagerberg, Gabriel Moruz
variants have been developed, the best of which are among the fastest generic sorting algorithms available, as testified by the choice of Quicksort as the default sorting algorithm in most...
Philip Bille, Rolf Fagerberg, Inge Li Gørtz
• The edit distance between two strings is the minimum number of insertions, deletions, and substitutions needed to convert one string to the other. E.g., edit-distance(“cocoa”, “cola”) =...
The Cost of Cache-Oblivious Searching Michael A. Bender (2008)
Gerth Sto/lting Brodal, Rolf Fagerberg, Dongdong Ge, Simai He, Haodong Hu, John Iacono
zx
Philip Bille, Rolf Fagerberg, Inge Li Gørtz
Abstract. We study the approximate string matching and regular expression matching problem for the case when the text to be searched is compressed with the Ziv-Lempel adaptive dictionary compression...
Philip Bille, Rolf Fagerberg, Inge Li Gørtz
Abstract. We study the approximate string matching and regular expression matching problem for the case when the text to be searched is compressed with the Ziv-Lempel adaptive dictionary compression...
Lars Arge, Gerth Stølting Brodal, Rolf Fagerberg
The memory system of most modern computers consists of a hierarchy of memory levels, with each level acting as a cache for the next; for a typical desktop computer the hierarchy consists of...
Rolf Fagerberg, Anna Pagh, Rasmus Pagh
Abstract. We give a randomized algorithm for sorting strings in external memory. For K binary strings comprising N words in total, our algorithm finds the sorted order and the longest common prefix...
Philip Bille, Rolf Fagerberg, Inge Li Gørtz
We study the approximate string matching and regular expression matching problem for the case when the text to be searched is compressed with the Ziv-Lempel adaptive dictionary compression schemes....
Optimal resilient dynamic dictionaries (2007)
Gerth Stølting Brodal, Rolf Fagerberg, Irene Finocchi, Fabrizio Gr, Allan Grønlund Jørgensen, Gabriel Moruz, ...
Abstract. We investigate the problem of computing in the presence of faults that may arbitrarily (i.e., adversarially) corrupt memory locations. In the faulty memory model, any memory cell can get...
Optimal resilient dynamic dictionaries (2007)
Gerth Stølting Brodal, Rolf Fagerberg, Allan Grønlund Jørgensen, Gabriel Moruz, Thomas Mølhave
Abstract. In the resilient memory model any memory cell can get corrupted at any time, and corrupted cells cannot be distinguished from uncorrupted cells. An upper bound, δ, on the number of...
Scheduling, 6(2):131–147, 2003. (2007)
Arne Andersson, Rolf Fagerberg, Yossi Azar, Joan Boyar, Leah Epstein, Lene M. Favrholdt, ...
on Accommodating Sequences for the Seat Reservation Problem. Journal of
Optimal resilient dynamic dictionaries (2007)
Gerth Stølting Brodal, Rolf Fagerberg, Irene Finocchi, Fabrizio Gr, Allan Grønlund Jørgensen, Gabriel Moruz, ...
Abstract. We investigate the problem of computing in the presence of faults that may arbitrarily (i.e., adversarially) corrupt memory locations. In the faulty memory model, any memory cell can get...
Bille, Philip, Fagerberg, Rolf, Goertz, Inge Li
We study the approximate string matching and regular expression matching problem for the case when the text to be searched is compressed with the Ziv-Lempel adaptive dictionary compression schemes....
Recrafting the neighbor-joining method (2006)
Mailund, Thomas, Brodal, Gerth S, Fagerberg, Rolf, Pedersen, Christian NS, Phillips, Derek
Abstract Background The neighbor-joining method by Saitou and Nei is a widely used method for constructing phylogenetic trees. The formulation of the method gives rise to a canonical Θ( n 3 )...
BMC Bioinformatics Methodology article Recrafting the neighbor-joining method (2006)
Thomas Mailund, Gerth S Brodal, Rolf Fagerberg, Christian Ns Pedersen, Derek Phillips
Background: The neighbor-joining method by Saitou and Nei is a widely used method for constructing phylogenetic trees. The formulation of the method gives rise to a canonical Θ(n3) algorithm upon...
Engineering a Cache-Oblivious Sorting Algorithm (2006)
Gerth Stølting Brodal, Rolf Fagerberg, Kristoffer Vinther
This paper is an algorithmic engineering study of cache-oblivious sorting. We investigate by empirical methods a number of implementation issues and parameter choices for the cache-oblivious sorting...
Cache-Oblivious Planar Orthogonal Range Searching and Counting (2005)
Lars Arge, Gerth Stølting Brodal, Morten Laustsen, Rolf Fagerberg
We present the first cache-oblivious data structure for planar orthogonal range counting, and improve on previous results for cache-oblivious planar orthogonal range searching. Our range counting...
G.: On the adaptiveness of quicksort (2005)
Gerth Stølting Brodal, Rolf Fagerberg, Gabriel Moruz
Quicksort was first introduced in 1961 by Hoare. Many variants have been developed, the best of which are among the fastest generic sorting algorithms available, as testified by the choice of...
G.: On the adaptiveness of quicksort (2005)
Gerth Stølting Brodal, Rolf Fagerberg, Gabriel Moruz
Quicksort was first introduced in 1961 by Hoare. Many variants have been developed, the best of which are among the fastest generic sorting algorithms available, as testified by the choice of...
Brodal, Gerth Stølting, Fagerberg, Rolf, Meyer, Ulrich, Zeh, Norbert, Hagerup, Torben, Katajainen, Jyrki
Gerth Sto/lting Brodal, Rolf Fagerberg, Ulrich Meyer, Norbert Zeh
Abstract. We present improved cache-oblivious data structures and algorithms for breadth-first search and the single-source shortest path problem on undirected graphs with non-negative edge weights....
Gerth Sto/lting Brodal, Rolf Fagerberg, Ulrich Meyer, Norbert Zeh
Abstract. We present improved cache-oblivious data structures and algorithms for breadth-first search and the single-source shortest path problem on undirected graphs with non-negative edge weights....
Gerth Stølting Brodal, Rolf Fagerberg, Ulrich Meyer, Norbert Zeh
of all or part of this workis permitted for educational or research use on condition that this copyright notice isincluded in any copy. See back inner page for a list of recent BRICS Report Series...
Gerth Stølting Brodal, Rolf Fagerberg, Ulrich Meyer, Norbert Zeh
Abstract. We present improved cache-oblivious data structures and algorithms for breadth-first search and the single-source shortest path problem on undirected graphs with non-negative edge weights....
Basic Research in Computer Science (2004)
On The Adaptiveness, Gerth Stølting Brodal, Rolf Fagerberg, Gabriel Moruz, Copyright C, Gerth Stølting Brodal, ...
Quicksort was first introduced in 1961 by Hoare. Many variants have been developed, the best of which are among the fastest generic sorting algorithms available, as testified by the choice of...
Copyright C, Gerth Stølting Brodal, Gerth Stølting Brodal, Gerth Stølting Brodal, Rolf Fagerberg, Rolf Fagerberg, ...
We present improved cache-oblivious data structures and algorithms for breadth-first search (BFS) on undirected graphs and the single-source shortest path (SSSP) problem on undirected graphs with...
This document in subdirectoryRS/04/27/ On the Adaptiveness of Quicksort (2004)
Gerth Stølting Brodal, Rolf Fagerberg, Gabriel Moruz, Copyright C, Gerth Stølting Brodal, Rolf Fagerberg, ...
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. See back inner page for a list of recent BRICS...
Copyright C, Gerth Stølting Brodal, Gerth Stølting Brodal, Gerth Stølting Brodal, Rolf Fagerberg, Rolf Fagerberg, ...
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. See back inner page for a list of recent BRICS...
Gerth Stølting Brodal, Rolf Fagerberg, Ulrich Meyer, Norbert Zeh
Abstract. We present improved cache-oblivious data structures and algorithms for breadth-first search and the single-source shortest path problem on undirected graphs with non-negative edge weights....
Brodal, Gerth Stølting, Fagerberg, Rolf, Meyer, Ulrich, Zeh, Norbert, Hagerup, Torben, Katajainen, Jyrki
On the limits of cache-obliviousness (2003)
Gerth Sto/lting Brodal, Rolf Fagerberg
Abstract In this paper, we present lower bounds for permuting and sorting in the cache-obliviousmodel. We prove that (1) I/O optimal cache-oblivious comparison based sorting is not possible without a...
Speeding up neighbour-joining tree construction (2003)
Gerth Stølting Brodal, Thomas Mailund, Derek Phillips, Rolf Fagerberg
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...
Lower bounds for external memory dictionaries (2003)
Gerth Sto/lting Brodal, Rolf Fagerberg
Abstract We study trade-offs between the update time and the query time for comparisonbased external memory dictionaries. The main contributions of this paper are two lower bound trade-offs between...
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...
The Cost of Cache-Oblivious Searching (2003)
Michael A. Bender, Gerth Stølting 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...
On the Limits of Cache-Obliviousness (2003)
Gerth Stølting 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...
Lower Bounds for External Memory Dictionaries (2003)
Gerth Stølting 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...
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...
Computing Refined Buneman Trees in Cubic Time (2002)
Gerth Stølting Brodal, Rolf Fagerberg, Anna Östlin, S. Srinivasa Rao
Abstract 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...
Cache oblivious distribution sweeping (2002)
Gerth Stølting Brodal, Rolf Fagerberg
Abstract 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...
Computing Refined Buneman Trees in Cubic Time (2002)
Gerth Sto/lting Brodal, Rolf Fagerberg
Abstract 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...
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 Distribution Sweeping (2002)
Gerth Stølting 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...
Funnel heap - a cache oblivious priority queue (2002)
Gerth Stølting 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...
Funnel Heap - A Cache Oblivious Priority Queue (2002)
Gerth Stølting 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...
This document in subdirectoryRS/02/51/ Computing Refined Buneman Trees in Cubic Time (2002)
Gerth Stølting Brodal, Rolf Fagerberg, Anna Östlin, S. Srinivasa Rao, Copyright C, ...
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. See back inner page for a list of recent BRICS...
Cache Oblivious Distribution Sweeping (2002)
Gerth Stølting 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...
Computing the quartet distance between evolutionary trees in time O(n log n (2001)
Gerth Stølting Brodal, Rolf Fagerberg
Abstract Evolutionary trees describing the relationship for a set of species are central in evolutionary biology, and quantifying differences between evolutionary trees is an important task. One...
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...
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...
Computing the quartet distance between evolutionary trees in time O(n log n (2001)
Gerth Sto/lting Brodal, Rolf Fagerberg, Christian N
n)
The complexity of constructing evolutionary trees using experiments (2001)
Gerth Sto/lting Brodal, Rolf Fagerberg, Christian N
\Lambda
Amortized Analysis of ...-Trees (2000)
Gerth Stølting 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...
Dynamic Representations of Sparse Graphs (1999)
Gerth Stølting 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...
Amortization Results for Chromatic Search Trees, with an Application to Priority Queues (1997)
Joan Boyar, Rolf Fagerberg, Kim S. Larsen
this paper, we prove that only an amortized constant amount of rebalancing is necessary after an update in a chromatic search tree. We also prove that the amount of rebalancing done at any particular...
A Generalization of Binomial Queues (1996)
We give a generalization of binomial queues involving an arbitrary sequence (mk )k=0;1;2;::: of integers greater than one. Different sequences lead to different worst case bounds for the priority...
A Generalization of Binomial Queues (1996)
We present a generalization of binomial queues, the definition of which involves a freely chosen sequence (m k ) k=0;1;2;::: of integers greater than one. Different sequences lead to different worst...
Optimal Rebalancing of Binary Search Trees (1996)
We give, for any reasonable function f , a scheme for rebalancing a binary search tree with amortized O(f(n)) work per update while guaranteeing a height bounded by dlog(n + 1) +1=f(n)e for all n. As...
A Note on Worst Case Efficient Meldable Priority Queues (1996)
We give a simple implementation of meldable priority queues, achieving Insert , Find min, and Meld in O(1) worst case time, and Delete min and Delete in O(log n) worst case time. 1 Introduction The...
Binary search trees: How low can you go? (1996)
We prove that no algorithm for balanced binary search trees performing insertions and deletions in amortized time O(f(n)) can guarantee a height smaller than dlog(n + 1) + 1=f(n)e for all n. We...
Amortization Results for Chromatic Search Trees, with an Application to Priority Queues (1995)
Joan Boyar, Rolf Fagerberg, Kim S. Larsen
this paper, we prove that, starting with an empty tree, i insertions and d deletions give rise to at most 3i + d \Gamma 2 rebalancing operations. We also show that the number of rebalancing...
B-Trees with Relaxed Balance (1995)
B-trees with relaxed balance have been defined to facilitate fast updating in a concurrent database environment. In that structure, updating and rebalancing are uncoupled such that extensive locking...
Chromatic Priority Queues (1994)
Joan Boyar, Rolf Fagerberg, Kim S. Larsen
We investigate the problem of implementing a priority queue to be used in a parallel environment, where asynchronous processes have access to a shared memory. Chromatic trees are a generalization of...
B-Trees with Relaxed Balance (1993)
B-trees with relaxed balance have been defined to facilitate fast updating on shared-memory asynchronous parallel architectures. To obtain this, rebalancing has been uncoupled from the updating such...
This document in subdirectoryRS/01/36/ Cache Oblivious Search Trees via Binary Trees of Small Height
Gerth Stølting Brodal, Rolf Fagerberg, Riko Jacob, Copyright C, Gerth Stølting Brodal, Rolf Fagerberg, ...
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. See back inner page for a list of recent BRICS...