115 citations · 430 across the 53 of their papers we have counts for
6 papers · 1 filter
Maximum independent sets in (pyramid, even hole)-free graphs
Maria Chudnovsky, Stéphan Thomassé, Nicolas Trotignon +1
A \emph{hole} in a graph is an induced cycle with at least 4 vertices. A graph is \emph{even-hole-free} if it does not contain a hole on an even number of vertices. A \emph{pyramid…
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…
Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs
Maria Chudnovsky, Marcin Pilipczuk, Michał Pilipczuk +1
In the Maximum Independent Set problem we are asked to find a set of pairwise nonadjacent vertices in a given graph with the maximum possible cardinality. In general graphs, this c…
The independent set problem is FPT for even-hole-free graphs
Edin Husic, Stephan Thomasse, Nicolas Trotignon
The class of even-hole-free graphs is very similar to the class of perfect graphs, and was indeed a cornerstone in the tools leading to the proof of the Strong Perfect Graph Theore…
Convexly independent subsets of Minkowski sums of convex polygons
Mateusz Skomra, Stéphan Thomassé
We show that there exist convex -gons and such that the largest convex polygon in the Minkowski sum has size . This matches an upper bound of Tiwary.
On the Maximum Weight Independent Set Problem in graphs without induced cycles of length at least five
Maria Chudnovsky, Marcin Pilipczuk, Michał Pilipczuk +1
A hole in a graph is an induced cycle of length at least , and an antihole is the complement of an induced cycle of length at least . A hole or antihole is long if its length…