Tillmann Miltzow

activity

20112026

\exists R

-complete

11 citations · 119 across the 41 of their papers we have counts for

collaborators

Showing 2014Show all

4 papers · 1 filter

cs.DM2014★ 1 cited

Counting K_4-Subdivisions

Tillmann Miltzow, Jens M. Schmidt, Mingji Xia

A fundamental theorem in graph theory states that any 3-connected graph contains a subdivision of $K_{4}$ . As a generalization, we ask for the minimum number of $K_{4}$ -subdivisions th…

cs.CG2014★ 1 cited

Halving Balls in Deterministic Linear Time

Michael Hoffmann, Vincent Kusters, Tillmann Miltzow

Let $\D$ be a set of $n$ pairwise disjoint unit balls in $R^{d}$ and $P$ the set of their center points. A hyperplane $\Hy$ is an \emph{ $m$ -separator} for $\D$ if each closed halfsp…

math.CO2014

Disjoint compatibility graph of non-crossing matchings of points in convex position

Oswin Aichholzer, Andrei Asinowski, Tillmann Miltzow

Let $X_{2 k}$ be a set of $2 k$ labeled points in convex position in the plane. We consider geometric non-intersecting straight-line perfect matchings of $X_{2 k}$ . Two such matchings…

math.CO2014

Counting Houses of Pareto Optimal Matchings in the House Allocation Problem

Andrei Asinowski, Balázs Keszegh, Tillmann Miltzow

Let $A, B$ with $∣ A ∣ = m$ and $∣ B ∣ = n \geq m$ be two sets. We assume that every element $a \in A$ has a reference list over all elements from $B$ . We call an injective mapping $τ$ fro…