Thumbnail
Access Restriction
Subscribed

Author Faenza, Yuri ♦ Oriolo, Gianpaolo ♦ Stauffer, Gautier
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2014
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Stable sets ♦ Claw-free graphs ♦ Decomposition
Abstract We propose an algorithm for solving the maximum weighted stable set problem on claw-free graphs that runs in $\textit{O}(|\textit{V}|(|\textit{E}|$ + $|\textit{V}|$ $log|\textit{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 $\textit{O}(|\textit{V}||\textit{E}|)-time$ algorithm that actually produces the decomposition.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2014-07-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 61
Issue Number 4
Page Count 41
Starting Page 1
Ending Page 41


Open content in new tab

   Open content in new tab
Source: ACM Digital Library