20 citations · 23 across the 21 of their papers we have counts for
6 papers · 1 filter
Adaptive Sorting, also in the BST Model
Ivor van der Hoog, Eva Rotenberg, Daniel Rutschmann
Sorting is one of the most basic algorithmic problems. Adaptive sorting algorithms exploit features that make an input easier to sort, often captured by entropy measures. Many such…
Near-Optimal Working-Set Heaps and Dijkstra on Pointer Machines
Ivor van der Hoog, John Iacono, Eva Rotenberg +1
A heap is a dynamic data structure that stores a set of labeled values under the following operations: pop returns the minimum value of the heap, Push() pushes a new value $x_…
Simpler Optimal Sorting from a Directed Acyclic Graph
Ivor van der Hoog, Eva Rotenberg, Daniel Rutschmann
Fredman proposed in 1976 the following algorithmic problem: Given are a ground set , some partial order over , and some comparison oracle that specifies a linear or…
Tight Bounds for Sorting Under Partial Information
Ivor van der Hoog, Daniel Rutschmann
Sorting has a natural generalization where the input consists of: (1) a ground set of size , (2) a partial oracle specifying some fixed partial order on and (3…
Adaptive Out-Orientations with Applications
Chandra Chekuri, Aleksander Bjørn Christiansen, Jacob Holm +4
We give improved algorithms for maintaining edge-orientations of a fully-dynamic graph, such that the out-degree of each vertex is bounded. On one hand, we show how to orient the e…
Adaptive Out-Orientations with Applications
Aleksander B. G. Christiansen, Jacob Holm, Ivor van der Hoog +2
We give improved algorithms for maintaining edge-orientations of a fully-dynamic graph, such that the out-degree of each vertex is bounded. On one hand, we show how to orient the e…