A Parallel Priority Queue with Constant Time Operations (2007)
Gerth St, Gerth St��lting Brodal, Jesper Larsson Traff, 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...
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...
Worst-Case Efficient External-Memory Priority Queues (1998)
Gerth St, 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...
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...
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...
Approximate Dictionary Queries (1996)
Gerth Stolting Brodal, Leszek Gasieniec, Gerth St��lting Brodal, Ny Munkegade
. Given a set of n binary strings of length m each. We consider the problem of answering d--queries. Given a binary query string ff of length m, a d--query is to report if there exists a string in...
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, 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...
The Randomized Complexity of Maintaining the Minimum (1996)
Gerth St Lting, 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...
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...
Priority Queues on Parallel Machines (1996)
Gerth St, 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...
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...
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...