11 citations · 19 across the 16 of their papers we have counts for
5 papers · 1 filter
The complexity of the Perfect Matching-Cut problem
Valentin Bouquet, Christophe Picouleau
Perfect Matching-Cut is the problem of deciding whether a graph has a perfect matching that contains an edge-cut. We show that this problem is NP-complete for planar graphs with ma…
Complexity and algorithms for constant diameter augmentation problems
Eun Jung Kim, Martin Milanic, Jérôme Monnot +1
We study the following problem: for given integers and graph , can we obtain a graph with diameter via at most edge deletions ? We determine the computational comp…
Partition of graphs with maximum degree ratio
Valentin Bouquet, François Delbot, Christophe Picouleau
Given a graph and a non trivial partition of its vertex-set, the satisfaction of a vertex is the ratio between the size of it's closed neighborhood in $V…
On Minimum Dominating Sets in cubic and (claw,H)-free graphs
Valentin Bouquet, François Delbot, Christophe Picouleau +1
Given a graph , is a dominating set if every is adjacent to an element of . The Minimum Dominating Set problem asks for a dominating…
The Minimum Dominating Set problem is polynomial for (claw, P8)-free graphs
Valentin Bouquet, Christophe Picouleau
We prove that the Minimum Dominating Set problem is polynomial for the class of (claw, P8)-free graphs.