1 citations · 1 across the 8 of their papers we have counts for
Showing 2022Show all
2 papers · 1 filter
cs.DS2022
Approximating Highly Inapproximable Problems on Graphs of Bounded Twin-Width
Pierre Bergé, Édouard Bonnet, Hugues Déprés +1
For any , we give a polynomial-time -approximation algorithm for Max Independent Set in graphs of bounded twin-width given with an -sequence.…
cs.CC2022
1-Extendability of independent sets
Pierre Bergé, Anthony Busson, Carl Feghali +1
In the 70s, Berge introduced 1-extendable graphs (also called B-graphs), which are graphs where every vertex belongs to a maximum independent set. Motivated by an application in th…