We propose an algorithm for solving the maximum weighted stable set problem on claw-free graphs that runs in O(|V|(|E| + |V| log|V|))-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(|V||E|)-time algorithm that actually produces the decomposition.
Faenza, Y., Oriolo, G., Stauffer, G. (2014). Solving the weighted stable set problem in claw-free graphs via decomposition. JOURNAL OF THE ASSOCIATION FOR COMPUTING MACHINERY, 61(4), 1-41 [10.1145/2629600].
Solving the weighted stable set problem in claw-free graphs via decomposition
ORIOLO, GIANPAOLO;
2014-01-01
Abstract
We propose an algorithm for solving the maximum weighted stable set problem on claw-free graphs that runs in O(|V|(|E| + |V| log|V|))-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(|V||E|)-time algorithm that actually produces the decomposition.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
