23 citations · 60 across the 50 of their papers we have counts for
6 papers · 1 filter
Uniquely restricted matchings and edge colorings
Julien Baste, Dieter Rautenbach, Ignasi Sau
A matching in a graph is uniquely restricted if no other matching covers exactly the same set of vertices. This notion was defined by Golumbic, Hirst, and Lewenstein and studied in…
Explicit linear kernels for packing problems
Valentin Garnero, Christophe Paul, Ignasi Sau +1
During the last years, several algorithmic meta-theorems have appeared (Bodlaender et al. [FOCS 2009], Fomin et al. [SODA 2010], Kim et al. [ICALP 2013]) guaranteeing the existence…
How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
Marin Bougeret, Ignasi Sau
In the last years, kernelization with structural parameters has been an active area of research within the field of parameterized complexity. As a relevant example, Gajarsk{y} et a…
Parameterized complexity of the MINCCA problem on graphs of bounded decomposability
Didem Gözüpek, Sibel Özkan, Christophe Paul +2
In an edge-colored graph, the cost incurred at a vertex on a path when two incident edges with different colors are traversed is called reload or changeover cost. The "Minimum Chan…
The number of labeled graphs of bounded treewidth
Julien Baste, Marc Noy, Ignasi Sau
We focus on counting the number of labeled graphs on vertices and treewidth at most (or equivalently, the number of labeled partial -trees), which we denote by …
Efficient FPT algorithms for (strict) compatibility of unrooted phylogenetic trees
Julien Baste, Christophe Paul, Ignasi Sau +1
In phylogenetics, a central problem is to infer the evolutionary relationships between a set of species ; these relationships are often depicted via a phylogenetic tree -- a tre…