11 citations · 119 across the 41 of their papers we have counts for
7 papers · 1 filter
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: (…
An Approximation Algorithm for the Art Gallery Problem
Édouard Bonnet, Tillmann Miltzow
Given a simple polygon on vertices, two points in are said to be visible to each other if the line segment between and is contained in…
Complexity of Token Swapping and its Variants
Édouard Bonnet, Tillmann Miltzow, Paweł Rzążewski
In the Token Swapping problem we are given a graph with a token placed on each vertex. Each token has exactly one destination vertex, and we try to move all the tokens to their des…
Peeling and Nibbling the Cactus: Subexponential-Time Algorithms for Counting Triangulations and Related Problems
Dániel Marx, Tillmann Miltzow
Given a set of points in the plane, a triangulation of is a maximal set of non-crossing segments with endpoints in . We present an algorithm that computes the nu…
The Parameterized Hardness of Art Gallery Problems
Édouard Bonnet, Tillmann Miltzow
Given a simple polygon on vertices, two points in are said to be visible to each other if the line segment between and is contained in…
Approximation and Hardness for Token Swapping
Tillmann Miltzow, Lothar Narins, Yoshio Okamoto +3
Given a graph with , we place on every vertex a token . A swap is an exchange of tokens on adjacent vertices. We consider the algorithmi…
Flip Distance to a Non-crossing Perfect Matching
Édouard Bonnet, Tillmann Miltzow
A perfect straight-line matching on a finite set of points in the plane is a set of segments such that each point in is an endpoint of exactly one segment. is non-c…