Rolf Fagerberg

Computing Refined Buneman Trees in Cubic Time (2003)

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

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

On the Limits of Cache-Obliviousness (2003)

Lower Bounds for External Memory Dictionaries (2002)

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

Cache Oblivious Search Trees via Binary Trees of Small Height (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...

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

Funnel Heap - A Cache Oblivious Priority Queue (2002)

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

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

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

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

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

Amortized Analysis of ...-Trees (2000)

Dynamic Representations of Sparse Graphs (1999)

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

Optimal Rebalancing of Binary Search Trees (1996)

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

Binary Search Trees: How Low Can You Go? (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...

Optimal Rebalancing of Binary Search Trees (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...

Binary Search Trees: How Low Can You Go? (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...

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

A Note on Worst Case Efficient Meldable Priority Queues (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...

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

A Generalization of Binomial 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...

B-Trees with Relaxed Balance (1995)

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

Kim S. Larsen, Rolf Fagerberg

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

B-Trees with Relaxed Balance (1995)

Kim S. Larsen, Rolf Fagerberg

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

Amortization Results for Chromatic Search Trees, with an Application to Priority Queues (1995)

A Generalization of Binomial Queues (1994)

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

A Generalization of Binomial Queues (1994)

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

A Generalization of Binomial Queues (1994)

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

Chromatic Priority Queues (1994)

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

Chromatic Priority Queues (1994)

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