{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:18:00Z","timestamp":1759637880126,"version":"3.41.0"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2014,7,1]],"date-time":"2014-07-01T00:00:00Z","timestamp":1404172800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Progetto di Eccellenza 2008&#8211;2009 of the Fondazione"},{"name":"Cassa di Risparmio di Padova e Rovigo"},{"name":"German Research Foundation (DFG)"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2014,7]]},"abstract":"<jats:p>\n            We propose an algorithm for solving the maximum weighted stable set problem on claw-free graphs that runs in\n            <jats:italic>O<\/jats:italic>\n            (|\n            <jats:italic>V<\/jats:italic>\n            |(|\n            <jats:italic>E<\/jats:italic>\n            | + |\n            <jats:italic>V<\/jats:italic>\n            | log|\n            <jats:italic>V<\/jats:italic>\n            |))-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\n            <jats:italic>O<\/jats:italic>\n            (|\n            <jats:italic>V<\/jats:italic>\n            ||\n            <jats:italic>E<\/jats:italic>\n            |)-time algorithm that actually produces the decomposition.\n          <\/jats:p>","DOI":"10.1145\/2629600","type":"journal-article","created":{"date-parts":[[2014,8,12]],"date-time":"2014-08-12T13:53:48Z","timestamp":1407851628000},"page":"1-41","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":35,"title":["Solving the Weighted Stable Set Problem in Claw-Free Graphs via Decomposition"],"prefix":"10.1145","volume":"61","author":[{"given":"Yuri","family":"Faenza","sequence":"first","affiliation":[{"name":"\u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne (EPFL)"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gianpaolo","family":"Oriolo","sequence":"additional","affiliation":[{"name":"Universit\u00e0 di Roma \u201cTor Vergata\u201d"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gautier","family":"Stauffer","sequence":"additional","affiliation":[{"name":"Grenoble INP"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,7]]},"reference":[{"volume-title":"Network Flows: Theory, Algorithms, and Applications","year":"1993","author":"Ahuja R.","key":"e_1_2_1_1_1"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-34611-8_6"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(02)00571-1"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.09.031"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"M. Chudnovsky and P. Seymour. 2005. The structure of claw-free graphs. In Surveys in Combinatorics 2005 London Mathematics Society. Lecture Note Series 327 153--171.  M. Chudnovsky and P. Seymour. 2005. The structure of claw-free graphs. In Surveys in Combinatorics 2005 London Mathematics Society . Lecture Note Series 327 153--171.","DOI":"10.1017\/CBO9780511734885.008"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2007.06.007"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2008.03.002"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2012.07.005"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/110847585"},{"key":"e_1_2_1_10_1","unstructured":"A. Dubois M. Rouire and G. Stauffer (supervisor). 2011. D\u00e9composition des graphes quasi-line et reduction du problem de couplage. Travail d\u2019Etude et de Recherche \u00e0 l\u2019Universit\u00e9 Bordeaux 2.  A. Dubois M. Rouire and G. Stauffer (supervisor). 2011. D\u00e9composition des graphes quasi-line et reduction du problem de couplage. Travail d\u2019Etude et de Recherche \u00e0 l\u2019Universit\u00e9 Bordeaux 2."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.6028\/jres.069B.013"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-008-2244-x"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1993.1052"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/320176.320229"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(01)00208-6"},{"volume-title":"Proceedings of ICALP","year":"2011","author":"Hermelin D.","key":"e_1_2_1_16_1"},{"key":"e_1_2_1_17_1","unstructured":"W. S. Kennedy and A. D. King. 2011. Finding a smallest odd hole in a claw-free graph using global structure. arXiv:1103.6222.  W. S. Kennedy and A. D. King. 2011. Finding a smallest odd hole in a claw-free graph using global structure. arXiv:1103.6222."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.v59:3"},{"key":"e_1_2_1_20_1","unstructured":"A. D. King and B. Reed. 2012. Claw-free graphs skeletal graphs and a stronger conjecture on \u03c9 \u0394 and \u03c7. http:\/\/arxiv.org\/abs\/1212.3036.  A. D. King and B. Reed. 2012. Claw-free graphs skeletal graphs and a stronger conjecture on \u03c9 \u0394 and \u03c7 . http:\/\/arxiv.org\/abs\/1212.3036."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.21679"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(00)00047-8"},{"key":"e_1_2_1_23_1","first-page":"75","article-title":"D\u00e9monstration nouvelle d\u2019un th\u00e9or\u00e8me de Whitney sur les r\u00e9seaux","volume":"50","author":"Krausz J.","year":"1943","journal-title":"Mat. Fix. Lapok"},{"key":"e_1_2_1_24_1","unstructured":"L. Lov\u00e1sz and M. D. Plummer. 1986. Matching Theory. North Holland Amsterdam.  L. Lov\u00e1sz and M. D. Plummer. 1986. Matching Theory . North Holland Amsterdam."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(80)90074-X"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.15807\/jorsj.44.194"},{"volume-title":"Proceedings of the 10th Cologne-Twente Workshop, 223--226","author":"Nobili P.","key":"e_1_2_1_27_1"},{"volume-title":"Proceedings of the 13th IPCO Conference. A. Lodi, A. Panconesi, and G. Rinaldi Eds., 77--96","author":"Oriolo G.","key":"e_1_2_1_28_1"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2011.12.029"},{"volume-title":"Proceedings of the 3rd IPCO Conference. G. Rinaldi and L. Wolsey Eds., 267--279","author":"Pulleyblank W. R.","key":"e_1_2_1_30_1"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(73)90029-X"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(90)90287-R"},{"volume-title":"Combinatorial optimization. Polyhedra and efficiency (3 volumes). Algorithms and Combinatorics 24","author":"Schrijver A.","key":"e_1_2_1_33_1"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2629600","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2629600","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:13:29Z","timestamp":1750227209000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2629600"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,7]]},"references-count":32,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,7]]}},"alternative-id":["10.1145\/2629600"],"URL":"https:\/\/doi.org\/10.1145\/2629600","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2014,7]]},"assertion":[{"value":"2011-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-07-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}