2 citations · 8 across the 11 of their papers we have counts for
4 papers · 1 filter
Enumerating minimal solution sets for metric graph problems
Benjamin Bergougnoux, Oscar Defrain, Fionn Mc Inerney
Problems from metric graph theory like Metric Dimension, Geodetic Set, and Strong Metric Dimension have recently had a strong impact in parameterized complexity by being the first…
Kernelization for Finding Lineal Topologies (Depth-First Spanning Trees) with Many or Few Leaves
Emmanuel Sam, Benjamin Bergougnoux, Petr A. Golovach +1
For a given graph , a depth-first search (DFS) tree of is an -rooted spanning tree such that every edge of is either an edge of or is between a \textit{descen…
Sparse Graphs of Twin-width 2 Have Bounded Tree-width
Benjamin Bergougnoux, Jakub Gajarský, Grzegorz Guśpiel +3
Twin-width is a structural width parameter introduced by Bonnet, Kim, Thomassé and Watrigant [FOCS 2020]. Very briefly, its essence is a gradual reduction (a contraction sequence)…
New Width Parameters for Independent Set: One-sided-mim-width and Neighbor-depth
Benjamin Bergougnoux, Tuukka Korhonen, Igor Razgon
We study the tractability of the maximum independent set problem from the viewpoint of graph width parameters, with the goal of defining a width parameter that is as general as pos…