4 papers · 1 filter
Decomposition horizons and a characterization of stable hereditary classes of graphs
Samuel Braunfeld, Jaroslav NeÅ¡etÅil, Patrice Ossona de Mendez +1
The notions of bounded-size and quasibounded-size decompositions with bounded treedepth base classes are central to the structural theory of graph sparsity introduced by two of the…
Advances in Algorithmic Meta Theorems
Sebastian Siebertz, Alexandre Vigny
Tractability results for the model checking problem of logics yield powerful algorithmic meta theorems of the form: Every computational problem expressible in a logic can be so…
Twin-width and permutations
Ãdouard Bonnet, Jaroslav NeÅ¡etÅil, Patrice Ossona de Mendez +2
Inspired by a width invariant on permutations defined by Guillemot and Marx, Bonnet, Kim, Thomassé, and Watrigant introduced the twin-width of graphs, which is a parameter describ…
Elimination distance to bounded degree on planar graphs
Alexander Lindermayr, Sebastian Siebertz, Alexandre Vigny
We study the graph parameter elimination distance to bounded degree, which was introduced by Bulian and Dawar in their study of the parameterized complexity of the graph isomorphis…