19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
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
- Dr. Yuri FAENZA Università di Padova
- Dr. Gautier STAUFFER University of Bordeaux 1
- Prof. Gianpaolo ORIOLO Università di Roma "Tor Vergata"