1 citations · 1 across the 9 of their papers we have counts for
16 papers
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_…
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…
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…
A Combinatorial Proof of Universal Optimality for Computing a Planar Convex Hull
Ivor van der Hoog, Eva Rotenberg, Daniel Rutschmann
For a planar point set , its convex hull is the smallest convex polygon that encloses all points in . The construction of the convex hull from an array containing i…
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…
Instance-Optimal Imprecise Convex Hull
Sarita de Berg, Ivor van der Hoog, Eva Rotenberg +2
Imprecise measurements of a point set P = (p1, ..., pn) can be modelled by a family of regions F = (R1, ..., Rn), where each imprecise region Ri contains a unique point pi. A retri…
Efficient Greedy Discrete Subtrajectory Clustering
Ivor van der Hoog, Lara Ost, Eva Rotenberg +1
We cluster a set of trajectories T using subtrajectories of T. Clustering quality may be measured by the number of clusters, the number of vertices of T that are absent from the cl…
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…
Triangulations Admit Dominating Sets of Size
Aleksander B. G. Christiansen, Eva Rotenberg, Daniel Rutschmann
We show that every planar triangulation on vertices has a dominating set of size . This approaches the bound conjectured by Matheson and Tarjan [MT'96], and…
Approximate Selection with Unreliable Comparisons in Optimal Expected Time
Shengyu Huang, Chih-Hung Liu, Daniel Rutschman
Given elements, an integer and a parameter , we study to select an element with rank in using unreliable comparisons where th…
Chains, Koch Chains, and Point Sets with many Triangulations
Daniel Rutschmann, Manuel Wettstein
We introduce the abstract notion of a chain, which is a sequence of points in the plane, ordered by -coordinates, so that the edge between any two consecutive points is unav…