1 citations · 2 across the 16 of their papers we have counts for
4 papers · 1 filter
Parameterized complexity of isometric path partition: treewidth and diameter
Dibyayan Chakraborty, Oscar Defrain, Florent Foucaud +2
We investigate the parameterized complexity of the Isometric Path Partition problem when parameterized by the treewidth () of the input graph, arguably one of the most…
A quasi-optimal upper bound for induced paths in sparse graphs
Basile Couëtoux, Oscar Defrain, Jean-Florent Raymond
In 2012, Nešetřil and Ossona de Mendez proved that graphs of bounded degeneracy that have a path of order also have an induced path of order . In this paper we…
Translating between the representations of an acyclic convex geometry of bounded degree
Oscar Defrain, Arthur Ohana, Simon Vilmin
We consider the problem of translating between irreducible closed sets and implicational bases in closure systems. To date, the complexity status of this problem is widely open, an…
Enumerating minimal dominating sets and variants in chordal bipartite graphs
Emanuel Castelo, Oscar Defrain, Guilherme C. M. Gomes
Enumerating minimal dominating sets with polynomial delay in bipartite graphs is a long-standing open problem. To date, even the subcase of chordal bipartite graphs is open, with t…