Gautier Stauffer, IBM Zurich Lab.
Abstract:
The weighted stable set problem in claw-free graphs is as generalization of the matching problem and can be solved in polynomial time. The current algorithms (Sbihi 80, Minty 80, Nakamura Tamura 01, Schrijver 03) are based on the augmenting path property inherited from matching. Lovasz and Plummer 86 proposed another type of algorithm based on graph reductions but unfortunately, this approach can only deal with the unweighted case. In this talk, we give a new algorithm based on graph reductions that allows to reduce the problem to a weighted matching problem, thus generalizing the approach by Lovasz and Plummer. u