Faenza, YuriOriolo, GianpaoloStauffer, Gautier2014-10-232014-10-232014-10-23201410.1145/2629600https://infoscience.epfl.ch/handle/20.500.14299/107936WOS:000340342000001We propose an algorithm for solving the maximum weighted stable set problem on claw-free graphs that runs in O(vertical bar V vertical bar (vertical bar E vertical bar+vertical bar V vertical bar log vertical bar V vertical bar))-time, drastically improving the previous best known complexity bound. This algorithm is based on a novel decomposition theorem for claw-free graphs, which is also introduced in the present article. Despite being weaker than the structural results for claw-free graphs given by Chudnovsky and Seymour [2005, 2008a, 2008b] our decomposition theorem is, on the other hand, algorithmic, that is, it is coupled with an O(vertical bar V vertical bar vertical bar E vertical bar)-time algorithm that actually produces the decomposition.AlgorithmsTheoryStable setsclaw-free graphsdecompositiontext::journal::journal article::research article