2 papers
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…