19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
Home > Timetable > Contribution details
PDF | XML

Solving the maximum weighted stable set problem in claw-free graphs via decomposition

Presented by Dr. Yuri FAENZA
Type: Oral presentation
Track: Algorithmic Graph Theory

Content

We propose an algorithm for solving the maximum weighted stable set problem in 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 we also present in this talk. Despite being weaker than the well-known structure result for claw-free graphs given by Chudnovsky and Seymour, our decomposition theorem is coupled with fast algorithm that actually produces the decomposition of the input graph.

Place

Location: Bled, Slovenia
Address: Best Western Hotel Kompas Bled

Primary authors

More