13 citations · 19 across the 6 of their papers we have counts for
23 papers
Twin-width V: linear minors, modular counting, and matrix multiplication
Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez +1
We continue developing the theory around the twin-width of totally ordered binary structures, initiated in the previous paper of the series. We first introduce the notion of parity…
Twin-width can be exponential in treewidth
Édouard Bonnet, Hugues Déprés
For any small positive real and integer , we build a graph with a vertex deletion set of size to a tree, and twin-width greater than $2…
Twin-width VIII: delineation and win-wins
Édouard Bonnet, Dibyayan Chakraborty, Eun Jung Kim +3
We introduce the notion of delineation. A graph class is said delineated if for every hereditary closure of a subclass of , it holds that $\ma…
EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs
Marthe Bonamy, Édouard Bonnet, Nicolas Bousquet +6
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…
Twin-width and polynomial kernels
Édouard Bonnet, Eun Jung Kim, Amadeus Reinald +2
We study the existence of polynomial kernels, for parameterized problems without a polynomial kernel on general graphs, when restricted to graphs of bounded twin-width. Our main re…
The Complexity of Mixed-Connectivity
Édouard Bonnet, Sergio Cabello
We investigate the parameterized complexity in and of determining whether a graph~ has a subset of vertices and edges whose removal disconnects , or disconnec…