Daniel Rutschmann

activity

20222026

most citedTriangulations Admit Dominating Sets of Size

2 n /7

1 citations · 1 across the 9 of their papers we have counts for

collaborators

Showing 2024Show all

2 papers · 1 filter

cs.DS2024

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 $X$ , some partial order $P$ over $X$ , and some comparison oracle $O_{L}$ that specifies a linear or…

cs.DS2024

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 $X$ of size $n$ , (2) a partial oracle $O_{P}$ specifying some fixed partial order $P$ on $X$ and (3…