10 papers
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_…
Instance and Universally Optimal Bounds for Imprecise Pareto Fronts
Sarita de Berg, Nynne Maria Foldager Bække, Frida Astrup Eriksen +3
In the imprecise geometry model, the input is an imprecise point set, which is a family of regions , where for each one may retrieve the true point $p_…
Sorting under Partial Information with Optimal Preprocessing Time via Unified Bound Heaps
Daniel Rutschmann
In 1972, Fredman proposes the problem of sorting under partial information: preprocess a directed acyclic graph with vertex set so that you can sort in t…
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…
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 Adaptive Bounds for Convex Hulls
Ivor van der Hoog, Eva Rotenberg, Daniel Rutschmann
Adaptive sorting algorithms exploit existing order in the input to obtain better-than-worst-case running times. A classical example is sorting by runs: if the input can be partitio…