1 citations · 1 across the 9 of their papers we have counts for
5 papers · 1 filter
Incremental Exact Vertex Connectivity
Felix Adena, Monika Henzinger, Christoph Kern +1
We study the problem of maintaining the vertex connectivity of a graph under edge insertions. For undirected graphs, our algorithm uses amortized time per edg…
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…
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…
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_…