Geometrical problems and computations General Terms (2009)
Lars Arge, Gerth Stølting Brodal, S. Srinivasa Rao
Point location is an extremely well-studied problem both in internal memory models and recently also in the external memory model. In this paper, we present an I/O-efficient dynamic data structure...
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...
Fast Allocation and Deallocation with an Improved Buddy System ∗ (2008)
Gerth Stølting 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...
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...
ARTICLE NO. PC981425 A Parallel Priority Queue with Constant Time Operations 1 (2008)
Gerth Stølting Brodal, Jesper Larsson Träff, 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...
Dynamic Matchings in Convex Bipartite Graphs (2008)
Gerth Stølting Brodal, Loukas Georgiadis, Kristoffer Arnsfelt Hansen, Irit Katriel
Abstract. We consider the problem of maintaining a maximum matching in a convex bipartite graph G = (V, E) under a set of update operations which includes insertions and deletions of vertices and...
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...
A Linear Time Algorithm for the k Maximal Sums Problem (2008)
Gerth Stølting Brodal, Allan Grønlund Jørgensen
Abstract. Finding the sub-vector with the largest sum in a sequence of n numbers is known as the maximum sum problem. Finding the k sub-vectors with the largest sums is a natural extension of this,...
ALCOMFT-TR-02-53 Cache Oblivious Search Trees via Binary Trees of Small (2008)
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 Matchings in Convex Bipartite Graphs (2008)
Gerth Stølting Brodal, Loukas Georgiadis, Kristoffer Arnsfelt Hansen, Irit Katriel
Abstract. We consider the problem of maintaining a maximum matching in a convex bipartite graph G = (V, E) under a set of update operations which includes insertions and deletions of vertices and...
An O(n log n) Version of the Averbakh-Berman Algorithm for the Robust Median of a Tree ⋆ (2008)
Gerth Stølting Brodal, Loukas Georgiadis, Irit Katriel
Abstract. We show that the minmax regret median of a tree can be found in O(nlog n) time. This is obtained by a modification of Averbakh and Berman’s O(nlog 2 n)-time algorithm: We design a dynamic...
Purely Functional Worst Case Constant Time Catenable Sorted Lists (2008)
Gerth Stølting Brodal, Christos Makris, Kostas Tsichlas
Abstract. We present a purely functional implementation of search trees that requires O(log n) time for search and update operations and supports the join of two trees in worst case constant time....
I/O-Efficient Dynamic Point Location in Monotone Planar Subdivisions (Extended Abstract) (2007)
Pankaj K. Agarwal, Lars Arge, Gerth Stølting Brodal, Jeffrey S. Vitter
) Pankaj K. Agarwal Lars Arge y Gerth Stølting Brodal z Jeffrey S. Vitter x Abstract We present an efficient external-memory dynamic data structure for point location in monotone planar...
Optimal Finger Search Trees in the Pointer Machine (2007)
Gerth Stølting Brodal, George Lagogiannis, Christos Makris, Gerth Stlting, Brodal George, Lagogiannis Christos Makris, ...
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...
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...
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...
The ComBack Method – Extending Hash Compaction with Backtracking (2007)
Michael Westergaard, Lars Michael Kristensen, Gerth Stølting Brodal, Lars Arge
Abstract. This paper presents the ComBack method for explicit state space exploration. The ComBack method extends the well-known hash compaction method such that full coverage of the state space is...
Dennis Søgaard, Gerth Stølting Brodal
ii In this thesis a short presentation of different solutions to solve the motion planning problem is done. The probabilistic road map approach is investigated further and the learning phase of this...
Jyrki Katajainen, Gerth Stølting Brodal, Hervé Brönnimann, Manuel Macías Córdoba, Miguel Fiandor Gutiérrez, Kasper Egdø, ...
This volume contains the papers presented at the 6th STL Workshop which was
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...
Faster Algorithms for Computing Longest Common Increasing Subsequences (2006)
Brodal, Gerth Stølting, Kaligosi, Kanela, Katriel, Irit, Kutz, Martin, Moshe, Lewenstein, Gabriel, Valiente
We present algorithms for finding a longest common increasing subsequence of two or more input sequences. For two sequences of lengths $m$ and $n$, where $m\ge n$, we present an algorithm with an...
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...
Gerth Stølting Brodal, Kanela Kaligosi, Irit Katriel, Martin Kutz, Martin Kutz, Gerth Stølting, ...
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 Planar Orthogonal Range Searching and Counting (2005)
Lars Arge, Gerth Stølting Brodal
We present the first cache-oblivious data structure for planar orthogonal range counting, and improve on previous results for cacheoblivious 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...
STXXL: Standard Template Library for XXL Data Sets (2005)
Dementiev, Roman, Kettner, Lutz, Sanders, Peter, Brodal, Gerth Stølting, Leonardi, Stefano
We present a software library \textsc{Stxxl}, that enables practice-oriented experimentation with huge data sets. \textsc{Stxxl} is an implementation of the C\texttt{++} standard template library STL...
Brodal, Gerth Stølting, Fagerberg, Rolf, Meyer, Ulrich, Zeh, Norbert, Hagerup, Torben, Katajainen, Jyrki
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
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...
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...
Fast Allocation and Deallocation with an Improved Buddy System (2003)
Gerth Stølting 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...
Gerth Stølting Brodal, Michael A. Bender, Dongdong Ge, Simai He, John Iacono (polytechnic, ...
– Cache oblivious model
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...
Solving the string statistics problem in time O(n log n) (2002)
Gerth Stølting Brodal, Rune B. Lyngsø, Anna Östlin
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...
Dynamic planar convex hull (2002)
Gerth Stølting 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 machine (2002)
Gerth Stølting Brodal, Athanasios Tsakalidis
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 in Time O(n log n) (2002)
Gerth Stølting Brodal, Rune B. Lyngsø, Anna Östlin, Ny Munkegade
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...
Optimal Finger Search Trees in the Pointer Machine (Extended Abstract) (2002)
Gerth Stølting Brodal, George Lagogiannis, Christos Makris, Athanasios Tsakalidis, Comp Eng, Inf Dept, ...
Gerth Stlting Brodal Dept. of Comp. Sci.
Dynamic planar convex hull (2002)
Gerth Stølting 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...
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...
Solving the String Statistics Problem in Time O(n log n) (2002)
Gerth Stølting Brodal, Rune B. Lyngsø, Anna Östlin
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...
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...
Dynamic planar convex hull (2002)
Gerth Stølting 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...
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)
Evolutionary trees describing the relationship for a set of species are central in evolutionary biology, and quantifying differences between evolutionary trees is therefore an important task. The...
Finding maximal quasiperiodicities in strings (2000)
Abstract. 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...
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 Planar Convex Hull with Optimal Query Time and O(log n log log n) Update Time (2000)
Gerth Stølting Brodal, Riko Jacob
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...
Pattern Matching in Dynamic Texts (2000)
Stephen Alstrup, Gerth Stølting 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)
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)....
On External-Memory MST, SSSP and Multi-way Planar Graph Separation (Extended Abstract) (2000)
Lars Arge, Gerth Stølting Brodal
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...
Improved bounds for dictionary look-up with one error (2000)
Copyright C, Gerth Stølting Brodal, Gerth Stølting Brodal, Srinivasan Venkatesh, Srinivasan Venkatesh, Gerth Stølting, ...
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...
Pattern matching in dynamic texts (2000)
Stephen Alstrup, Gerth Stølting 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.,...
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...
Finding Maximal Pairs with Bounded Gap (1999)
Gerth Stølting Brodal, RUNE BANG Lyngsø, Christian Nrgaard, Storm Pedersen
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, and...
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 Pairs with Bounded Gap (1999)
Gerth Stølting 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 different. The...
Finding maximal pairs with bounded gap (1999)
Gerth Stølting Brodal, Christian Nørgaard, Storm Pedersen
ABSTRACT: 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...
Comparator Networks for Binary Heap Construction (1998)
Gerth Stølting 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...
Comparator Networks for Binary Heap Construction (1998)
Gerth Stølting Brodal, M. Cristina Pinotti, Gerth St��lting Brodal
. 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 (1998)
Gerth Stølting Brodal, Gerth St��lting Brodal
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 (1998)
Gerth Stølting Brodal, Gerth St��lting Brodal, Jesper Larsson Träff, 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 Stølting Brodal, Jesper Larsson Träff, Christos D. Zaroliagis, Im Stadtwald
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...
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...
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...
A Parallel Priority Data Structure with Applications (1997)
Gerth Stølting Brodal, Jesper Larsson Träff, Gerth St��lting Brodal, Jesper Larsson, Tr Christos, 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...
Worst Case Efficient Data Structures (1997)
Gerth Stølting Brodal, Gerth St��lting Brodal, Gerth St��lting Brodal
We study the design of efficient data structures. In particular we focus on the design of data structures where each operation has a worst case efficient implementations. The concrete problems we...
Worst-Case Efficient External-Memory Priority Queues (1997)
Gerth Stølting Brodal, Gerth St��lting Brodal, Im Stadtwald, Jyrki Katajainen
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...
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)
Gerth Stølting 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...
Priority Queues on Parallel Machines (1996)
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 Priority Queues (1996)
Gerth Stølting Brodal, Gerth St��lting Brodal
An implementation of priority queues is presented that supports the operations MakeQueue, FindMin, Insert, Meld and DecreaseKey in worst case time O(1) and DeleteMin and Delete in worst case time...
The Randomized Complexity of Maintaining the Minimum (1996)
Gerth Stølting 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...
Partially Persistent Data Structures Of Bounded Degree With Constant Update Time (1996)
Gerth Stølting Brodal, Gerth St��lting Brodal
. The problem of making bounded in-degree and out-degree data structures partially persistent is considered. The node copying method of Driscoll et al. is extended so that updates can be performed in...
Optimal Purely Functional Priority Queues (1996)
Gerth Stølting Brodal, Gerth St��lting Brodal, Chris Okasaki
Brodal recently introduced the first implementation of imperative priority queues to support findMin, insert, and meld in O(1) worst-case time, and deleteMin in O(log n) worstcase time. These bounds...
A Communication Complexity Proof that Symmetric Functions have Logarithmic Depth (1996)
Gerth Stølting Brodal, Gerth St��lting Brodal, Thore Husfeldt
. We present a direct protocol with logarithmic communication that finds an element in the symmetric difference of two sets of different size. This yields a simple proof that symmetric functions have...
The Randomized Complexity of Maintaining the Minimum (1996)
Gerth Stølting Brodal, Shiva Chaudhuri, Jaikumar Radhakrishnan, Gerth St��lting 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...
Priority Queues on Parallel Machines (1996)
Gerth Stølting Brodal, Gerth St��lting Brodal
. 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...
Gerth Stølting Brodal, Sven Skyum, Gerth Stølting Brodal
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...
Optimal purely functional priority queues (1996)
Gerth Stølting Brodal, Gerth Stølting Brodal, Chris Okasaki, Chris Okasaki
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...
The randomized complexity of maintaining the minimum (1996)
Gerth Stølting Brodal, Gerth Stølting Brodal, Shiva Chaudhuri, Shiva Chaudhuri, Jaikumar Radhakrishnan, Jaikumar Radhakrishnan
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...
Fast Meldable Priority Queues (1995)
Gerth Stølting Brodal, Gerth St��lting Brodal
. We present priority queues that support the operations FindMin, Insert, MakeQueue and Meld in worst case time O(1) and Delete and DeleteMin in worst case time O(log n). They can be implemented on...
This document in subdirectoryRS/99/12/
Gerth Stølting Brodal, Rune B. Lyngsø, Jens Stoye, Copyright C, Gerth Stølting Brodal, ...
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...
This document in subdirectoryRS/99/25/
Gerth Stølting Brodal, Copyright C, Gerth Stølting Brodal, Christian N. S, Gerth Stølting, ...
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...
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...
A COMMUNICATION COMPLEXITY PROOF THAT
Gerth Stølting Brodal, Thore Husfeldt
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...