33 citations · 242 across the 67 of their papers we have counts for
4 papers · 1 filter
When Maximum Stable Set can be solved in FPT time
Édouard Bonnet, Nicolas Bousquet, Stéphan Thomassé +1
Maximum Independent Set (MIS for short) is in general graphs the paradigmatic -hard problem. In stark contrast, polynomial-time algorithms are known when the inputs are restr…
Linear transformations between colorings in chordal graphs
Nicolas Bousquet, Valentin Bartier
Let and be such that . Consider two -colorings of a -degenerate graph . Can we transform one into the other by recoloring one vertex at each step while…
The Perfect Matching Reconfiguration Problem
Marthe Bonamy, Nicolas Bousquet, Marc Heinrich +5
We study the perfect matching reconfiguration problem: Given two perfect matchings of a graph, is there a sequence of flip operations that transforms one into the other? Here, a fl…
A polynomial version of Cereceda's conjecture
Nicolas Bousquet, Marc Heinrich
Let and be such that . Consider two -colourings of a -degenerate graph . Can we transform one into the other by recolouring one vertex at each step whil…