13 citations · 95 across the 28 of their papers we have counts for
7 papers · 1 filter
Solving Problems on Generalized Convex Graphs via Mim-Width
Flavia Bonomo-Braberman, Nick Brettell, Andrea Munaro +1
A bipartite graph is -convex, for some family of graphs , if there exists a graph with such that the set of neighbours in $…
List -Colouring -Free Graphs: a Mim-width Perspective
Nick Brettell, Jake Horsfield, Andrea Munaro +1
A colouring of a graph is a mapping such that for every two adjacent vertices and of . The {\sc List -Colourin…
Close relatives of Feedback Vertex Set without single-exponential algorithms parameterized by treewidth
Benjamin Bergougnoux, Édouard Bonnet, Nick Brettell +1
The Cut & Count technique and the rank-based approach have lead to single-exponential FPT algorithms parameterized by treewidth, that is, running in time , for F…
Computing Weighted Subset Transversals in -Free Graphs
Nick Brettell, Matthew Johnson, Daniel Paulusma
For the Odd Cycle Transversal problem, the task is to find a small set of vertices in a graph that intersects every cycle of odd length. The Subset Odd Cycle Transversal proble…
Colouring -Free Graphs: a Mim-Width Perspective
Nick Brettell, Jake Horsfield, Daniel Paulusma
We prove that the class of -free graphs has bounded mim-width for every and , and that there is a polynomial-time algorithm that, given a graph i…
Steiner Trees for Hereditary Graph Classes: a Treewidth Perspective
Hans Bodlaender, Nick Brettell, Matthew Johnson +3
We consider the classical problems (Edge) Steiner Tree and Vertex Steiner Tree after restricting the input to some class of graphs characterized by a small set of forbidden induced…
Bounding the Mim-Width of Hereditary Graph Classes
Nick Brettell, Jake Horsfield, Andrea Munaro +2
A large number of NP-hard graph problems become polynomial-time solvable on graph classes where the mim-width is bounded and quickly computable. Hence, when solving such problems o…