Tillmann Miltzow

activity

20112026

\exists R

-complete

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

collaborators

Showing math.COShow all

3 papers · 1 filter

math.CO2015

Upper and Lower Bounds on Long Dual-Paths in Line Arrangements

Udo Hoffmann, Linda Kleist, Tillmann Miltzow

Given a line arrangement $A$ with $n$ lines, we show that there exists a path of length $n^{2} /3 - O (n)$ in the dual graph of $A$ formed by its faces. This bound is tight u…

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…