15 citations · 87 across the 33 of their papers we have counts for
6 papers · 1 filter
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…
The Parameterized Complexity of Positional Games
Édouard Bonnet, Serge Gaspers, Antonin Lambilliotte +2
We study the parameterized complexity of several positional games. Our main result is that Short Generalized Hex is W[1]-complete parameterized by the number of moves. This solves…
Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms
Édouard Bonnet, Nick Brettell, O-joung Kwon +1
It has long been known that Feedback Vertex Set can be solved in time on -vertex graphs of treewidth , but it was only recently t…