12 citations · 46 across the 17 of their papers we have counts for
5 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…
Sublinear Longest Path Transversals
James A. Long, Kevin G. Milans, Andrea Munaro
We show that connected graphs admit sublinear longest path transversals. This improves an earlier result of Rautenbach and Sereni and is related to the fifty-year-old question of w…
Approximating Independent Set and Dominating Set on VPG graphs
Esther Galby, Andrea Munaro
We consider Independent Set and Dominating Set restricted to VPG graphs (or, equivalently, string graphs). We show that they both remain -hard on -VPG graphs admi…
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…