1 citations · 2 across the 20 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_…
Tight Better-Than-Worst-Case Bounds for Element Distinctness and Set Intersection
Ivor van der Hoog, Eva Rotenberg, Daniel Rutschmann
The element distinctness problem takes as input a list of values from a totally ordered universe and the goal is to decide whether contains any duplicates. It is a well…
Simpler Universally Optimal Dijkstra
Ivor van der Hoog, Eva Rotenberg, Daniel Rutschmann
Let G be a weighted (directed) graph with n vertices and m edges. Given a source vertex s, Dijkstra's algorithm computes the shortest path lengths from s to all other vertices in O…
Local Density and its Distributed Approximation
Aleksander Bjørn Christiansen, Ivor van der Hoog, Eva Rotenberg
The densest subgraph problem is a classic problem in combinatorial optimisation. Danisch, Chan, and Sozio propose a definition for \emph{local density} that assigns to each vertex…
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…