1 citations · 2 across the 16 of their papers we have counts for
5 papers · 1 filter
Local certification of geometric graph classes
Oscar Defrain, Louis Esperet, Aurélie Lagoutte +2
The goal of local certification is to locally convince the vertices of a graph that satisfies a given property. A prover assigns short certificates to the vertices of the g…
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…
On the hardness of inclusion-wise minimal separators enumeration
Caroline Brosse, Oscar Defrain, Kazuhiro Kurita +3
Enumeration problems are often encountered as key subroutines in the exact computation of graph parameters such as chromatic number, treewidth, or treedepth. In the case of treedep…
Hypergraph dualization with FPT-delay parameterized by the degeneracy and dimension
Valentin Bartier, Oscar Defrain, Fionn Mc Inerney
At STOC 2002, Eiter, Gottlob, and Makino presented a technique called ordered generation that yields an -delay algorithm listing all minimal transversals of an -vertex…
Sparse graphs without long induced paths
Oscar Defrain, Jean-Florent Raymond
Graphs of bounded degeneracy are known to contain induced paths of order when they contain a path of order , as proved by Nešetřil and Ossona de Mendez (2012).…