8 citations · 11 across the 16 of their papers we have counts for
4 papers · 1 filter
Moderately beyond clique-width: reduced component max-leaf and related parameters
Édouard Bonnet, Yeonsu Chang, Julien Duron +2
Reduced parameters [BKW, JCTB '26; BKRT, SODA '22] are defined via contraction sequences. Based on this framework, we introduce the reduced component max-leaf, denoted by $\operato…
Fast Shortest Path in Graphs With Sparse Signed Tree Models and Applications
Édouard Bonnet, Colin Geniet, Eun Jung Kim +1
A signed tree model of a graph is a compact binary structure consisting of a rooted binary tree whose leaves are bijectively mapped to the vertices of , together with 2-colo…
Maximum Independent Set when excluding an induced minor: and
Édouard Bonnet, Julien Duron, Colin Geniet +2
Dallard, Milanič, and Štorgel [arXiv '22] ask if for every class excluding a fixed planar graph as an induced minor, Maximum Independent Set can be solved in polynomial time, a…
Twin-width III: Max Independent Set, Min Dominating Set, and Coloring
Édouard Bonnet, Colin Geniet, Eun Jung Kim +2
We recently introduced the graph invariant twin-width, and showed that first-order model checking can be solved in time for -vertex graphs given with a witness that th…