An algorithmic decomposition of claw-free graphs leading to an O(n^3) algorithm for the weighted stable set problem

Other literature type, Conference object English OPEN
Faenza, Y.; Oriolo, G.; Stauffer, G.;
(2011)
  • Publisher: SIAM
  • Subject:
    arxiv: Computer Science::Discrete Mathematics | Mathematics::Combinatorics

We propose an algorithm for solving the maximum weighted stable set problem on claw-free graphs that runs in O(n^3)-time, drastically improving the previous best known complexity bound. This algorithm is based on a novel decomposition theorem for claw-free graphs, which... View more
Share - Bookmark