Solving the Weighted Stable Set Problem in Claw-Free Graphs via Decomposition

We 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.


Published in:
Journal Of The Acm, 61, 4
Year:
2014
Publisher:
New York, Assoc Computing Machinery
ISSN:
0004-5411
Keywords:
Laboratories:




 Record created 2014-10-23, last modified 2018-03-17


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)