15 citations · 87 across the 33 of their papers we have counts for
9 papers · 1 filter
Maximum Clique in Disk-Like Intersection Graphs
Édouard Bonnet, Nicolas Grelier, Tillmann Miltzow
We study the complexity of Maximum Clique in intersection graphs of convex objects in the plane. On the algorithmic side, we extend the polynomial-time algorithm for unit disks [Cl…
Maximum Matchings in Geometric Intersection Graphs
Édouard Bonnet, Sergio Cabello, Wolfgang Mulzer
Let be an intersection graph of geometric objects in the plane. We show that a maximum matching in can be found in time with high probability, wher…
EPTAS for Max Clique on Disks and Unit Balls
Marthe Bonamy, Édouard Bonnet, Nicolas Bousquet +2
We propose a polynomial-time algorithm which takes as input a finite set of points of and compute, up to arbitrary precision, a maximum subset with diameter at most $…
Optimality program in segment and string graphs
Édouard Bonnet, Paweł Rzążewski
Planar graphs are known to allow subexponential algorithms running in time or for most of the paradigmatic problems, while the brute-force…
QPTAS and Subexponential Algorithm for Maximum Clique on Disk Graphs
Édouard Bonnet, Panos Giannopoulos, Eun Jung Kim +2
A (unit) disk graph is the intersection graph of closed (unit) disks in the plane. Almost three decades ago, an elegant polynomial-time algorithm was found for \textsc{Maximum Cliq…
On the Parameterized Complexity of Red-Blue Points Separation
Édouard Bonnet, Panos Giannopoulos, Michael Lampis
We study the following geometric separation problem: Given a set of red points and a set of blue points in the plane, find a minimum-size set of lines that separate fro…
Orthogonal Terrain Guarding is NP-complete
Édouard Bonnet, Panos Giannopoulos
A terrain is an x-monotone polygonal curve, i.e., successive vertices have increasing x-coordinates. Terrain Guarding can be seen as a special case of the famous art gallery proble…
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…
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…