135 citations · 346 across the 10 of their papers we have counts for
13 papers
Resolving Envy by Adding Goods with Bounded Supply: A Type-Count Dichotomy and Two-Agent Hardness
Chuang-Chieh Lin, Guillaume Fertin, Po-An Chen +4
We study envy elimination by adding goods (EEAG) when the additional pool has bounded supply and no separate budget bound. We establish a sharp type-count dichotomy for binary addi…
Sorting Genomes by Prefix Double-Cut-and-Joins
Guillaume Fertin, Géraldine Jean, Anthony Labarre
In this paper, we study the problem of sorting unichromosomal linear genomes by prefix double-cut-and-joins (or DCJs) in both the signed and the unsigned settings. Prefix DCJs cut…
Graph Motif Problems Parameterized by Dual
Guillaume Fertin, Christian Komusiewicz
Let be a vertex-colored graph, where is the set of colors used to color . The Graph Motif (or GM) problem takes as input , a multiset of colors built from $…
Finding a Small Number of Colourful Components
Laurent Bulteau, Konrad K. Dabrowski, Guillaume Fertin +3
A partition of the vertex set of a graph with a (not necessarily proper) colouring is colourful if no two vertices in any have the same colour and…
The Maximum Colorful Arborescence problem parameterized by the structure of its color hierarchy graph
Guillaume Fertin, Julien Fradin, Christian Komusiewicz
Let G=(V,A) be a vertex-colored arc-weighted directed acyclic graph (DAG) rooted in some vertex r, and let H be its color hierarchy graph, defined as follows: V(H) is the color set…
Decomposing Cubic Graphs into Connected Subgraphs of Size Three
Laurent Bulteau, Guillaume Fertin, Anthony Labarre +2
Let be the set of connected graphs of size 3. We study the problem of partitioning the edge set of a graph into graphs taken from any non-empty $S'\subs…