7 citations · 10 across the 6 of their papers we have counts for
6 papers
Avoider-Enforcer Game is NP-hard
Tillmann Miltzow, Miloš Stojaković
In an Avoider-Enforcer game, we are given a hypergraph. Avoider and Enforcer alternate in claiming an unclaimed vertex, until all the vertices of the hypergraph are claimed. Enforc…
Irrational Guards are Sometimes Needed
Mikkel Abrahamsen, Anna Adamaszek, Tillmann Miltzow
In this paper we study the art gallery problem, which is one of the fundamental problems in computational geometry. The objective is to place a minimum number of guards inside a si…
Intersection Graphs of Rays and Grounded Segments
Jean Cardinal, Stefan Felsner, Tillmann Miltzow +2
We consider several classes of intersection graphs of line segments in the plane and prove new equality and separation results between those classes. In particular, we show that: (…
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 . As a generalization, we ask for the minimum number of -subdivisions th…
Halving Balls in Deterministic Linear Time
Michael Hoffmann, Vincent Kusters, Tillmann Miltzow
Let $\D$ be a set of pairwise disjoint unit balls in and the set of their center points. A hyperplane $\Hy$ is an \emph{-separator} for $\D$ if each closed halfsp…
Disjoint compatibility graph of non-crossing matchings of points in convex position
Oswin Aichholzer, Andrei Asinowski, Tillmann Miltzow
Let be a set of labeled points in convex position in the plane. We consider geometric non-intersecting straight-line perfect matchings of . Two such matchings…