{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T14:49:37Z","timestamp":1770994177100,"version":"3.50.1"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2020,6,17]],"date-time":"2020-06-17T00:00:00Z","timestamp":1592352000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,6,17]],"date-time":"2020-06-17T00:00:00Z","timestamp":1592352000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-17-CE40-0015"],"award-info":[{"award-number":["ANR-17-CE40-0015"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-17-CE40-0015"],"award-info":[{"award-number":["ANR-17-CE40-0015"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,8]]},"DOI":"10.1007\/s00453-020-00730-6","type":"journal-article","created":{"date-parts":[[2020,6,17]],"date-time":"2020-06-17T08:02:47Z","timestamp":1592380967000},"page":"2360-2394","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Parameterized Complexity of Independent Set in H-Free Graphs"],"prefix":"10.1007","volume":"82","author":[{"given":"\u00c9douard","family":"Bonnet","sequence":"first","affiliation":[]},{"given":"Nicolas","family":"Bousquet","sequence":"additional","affiliation":[]},{"given":"Pierre","family":"Charbit","sequence":"additional","affiliation":[]},{"given":"St\u00e9phan","family":"Thomass\u00e9","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6243-5910","authenticated-orcid":false,"given":"R\u00e9mi","family":"Watrigant","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,6,17]]},"reference":[{"key":"730_CR1","unstructured":"Alekseev, V.E.: The effect of local constraints on the complexity of determination of the graph independence number. Combinatorial-Algebraic Methods in Applied Mathematics pp. 3\u201313 (1982). In Russian"},{"key":"730_CR2","unstructured":"Alekseev, V.E.: On the number of maximal independent sets in graphs from hereditary classes. In: Combinatorial-Algebraic Methods in Discrete Optimization, pp. 5\u20138 (1991) (in Russian)"},{"issue":"2","key":"730_CR3","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1007\/s00453-018-0479-5","volume":"81","author":"G Bacs\u00f3","year":"2019","unstructured":"Bacs\u00f3, G., Lokshtanov, D., Marx, D., Pilipczuk, M., Tuza, Z., van Leeuwen, E.J.: Subexponential-time algorithms for maximum independent set in P\\_t-free and broom-free graphs. Algorithmica 81(2), 421\u2013438 (2019). https:\/\/doi.org\/10.1007\/s00453-018-0479-5","journal-title":"Algorithmica"},{"issue":"1","key":"730_CR4","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/120880240","volume":"28","author":"HL Bodlaender","year":"2014","unstructured":"Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Kernelization lower bounds by cross-composition. SIAM J. Discrete Math. 28(1), 277\u2013305 (2014)","journal-title":"SIAM J. Discrete Math."},{"key":"730_CR5","doi-asserted-by":"publisher","unstructured":"Bonnet, \u00c9., Bousquet, N., Thomass\u00e9, S., Watrigant, R.: When maximum stable set can be solved in FPT time. In: Lu, P., Zhang, G. (eds.) 30th International Symposium on Algorithms and Computation, ISAAC 2019, LIPIcs, vol. 149, pp. 49:1\u201349:22. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019). https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2019.49","DOI":"10.4230\/LIPIcs.ISAAC.2019.49"},{"key":"730_CR6","doi-asserted-by":"crossref","unstructured":"Cai, L., Chan, S.M., Chan, S.O.: Random separation: a new method for solving fixed-cardinality optimization problems. In: Proceedings of the 2nd International Workshop on Parameterized and Exact Computation (IWPEC), pp. 239\u2013250 (2006)","DOI":"10.1007\/11847250_22"},{"issue":"1","key":"730_CR7","doi-asserted-by":"publisher","first-page":"6:1","DOI":"10.1145\/2071379.2071385","volume":"8","author":"J Chen","year":"2012","unstructured":"Chen, J., Liu, Y., Lu, S., Sze, S., Zhang, F.: Iterative expansion and color coding: an improved algorithm for 3d-matching. ACM Trans. Algorithms 8(1), 6:1\u20136:22 (2012). https:\/\/doi.org\/10.1145\/2071379.2071385","journal-title":"ACM Trans. Algorithms"},{"issue":"4","key":"730_CR8","doi-asserted-by":"publisher","first-page":"926","DOI":"10.1137\/0214065","volume":"14","author":"DG Corneil","year":"1985","unstructured":"Corneil, D.G., Perl, Y., Stewart, L.K.: A linear recognition algorithm for cographs. SIAM J. Comput. 14(4), 926\u2013934 (1985)","journal-title":"SIAM J. Comput."},{"key":"730_CR9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015)"},{"key":"730_CR10","unstructured":"Dabrowski, K.: Structural solutions to maximum independent set and related problems. Ph.D. thesis, University of Warwick (2012)"},{"key":"730_CR11","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/j.jda.2011.12.012","volume":"14","author":"K Dabrowski","year":"2012","unstructured":"Dabrowski, K., Lozin, V.V., M\u00fcller, H., Rautenbach, D.: Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number. J. Discrete Algorithms 14, 207\u2013213 (2012)","journal-title":"J. Discrete Algorithms"},{"key":"730_CR12","volume-title":"Graph Theory, 4th Edition, Graduate Texts in Mathematics","author":"R Diestel","year":"2012","unstructured":"Diestel, R.: Graph Theory, 4th Edition, Graduate Texts in Mathematics, vol. 173. Springer, Berlin (2012)"},{"key":"730_CR13","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity. Texts in Computer Science","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, Berlin (2013)"},{"issue":"2","key":"730_CR14","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1016\/j.disc.2017.09.012","volume":"341","author":"HP du Cray","year":"2018","unstructured":"du Cray, H.P., Sau, I.: Improved FPT algorithms for weighted independent set in bull-free graphs. Discrete Math. 341(2), 451\u2013462 (2018)","journal-title":"Discrete Math."},{"key":"730_CR15","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York (1979)"},{"key":"730_CR16","doi-asserted-by":"publisher","unstructured":"Grzesik, A., Klimo\u0161ov\u00e1, T., Pilipczuk, M., Pilipczuk, M.: Polynomial-time algorithm for maximum weight independent set on p6-free graphs. In: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, 6\u20139 January 2019, pp. 1257\u20131271 (2019). https:\/\/doi.org\/10.1137\/1.9781611975482.77","DOI":"10.1137\/1.9781611975482.77"},{"issue":"3","key":"730_CR17","first-page":"513","volume":"70","author":"D Hermelin","year":"2014","unstructured":"Hermelin, D., Mnich, M., van Leeuwen, E.J.: Parameterized complexity of induced graph matching on claw-free graphs. Algorithmica 70(3), 513\u2013560 (2014)","journal-title":"Algorithmica"},{"issue":"2","key":"730_CR18","doi-asserted-by":"publisher","first-page":"612","DOI":"10.1007\/s10878-016-0096-7","volume":"34","author":"T Karthick","year":"2017","unstructured":"Karthick, T.: Independent sets in some classes of S$$_{i, j, k}$$-free graphs. J. Comb. Optim. 34(2), 612\u2013630 (2017)","journal-title":"J. Comb. Optim."},{"key":"730_CR19","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/j.dam.2015.02.012","volume":"216","author":"T Karthick","year":"2017","unstructured":"Karthick, T., Maffray, F.: Maximum weight independent sets in classes related to claw-free graphs. Discrete Appl. Math. 216, 233\u2013239 (2017)","journal-title":"Discrete Appl. Math."},{"key":"730_CR20","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Vatshelle, M., Villanger, Y.: Independent set in P$${}_{\\text{5}}$$-free graphs in polynomial time. Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, pp. 570\u2013581 (2014)","DOI":"10.1137\/1.9781611973402.43"},{"key":"730_CR21","doi-asserted-by":"publisher","unstructured":"Marx, D.: Parameterized complexity of independence and domination on geometric graphs. In: Parameterized and Exact Computation, Second International Workshop, IWPEC 2006, Z\u00fcrich, Switzerland, 13\u201315 September 2006, Proceedings, pp. 154\u2013165 (2006). https:\/\/doi.org\/10.1007\/11847250_14","DOI":"10.1007\/11847250_14"},{"issue":"3","key":"730_CR22","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1016\/0095-8956(80)90074-X","volume":"28","author":"GJ Minty","year":"1980","unstructured":"Minty, G.J.: On maximal independent sets of vertices in claw-free graphs. J. Comb. Theory Ser. B 28(3), 284\u2013304 (1980)","journal-title":"J. Comb. Theory Ser. B"},{"key":"730_CR23","doi-asserted-by":"publisher","unstructured":"Naor, M., Schulman, L.J., Srinivasan, A.: Splitters and near-optimal derandomization. In: Proceedings of IEEE 36th Annual Foundations of Computer Science, pp. 182\u2013191 (1995). https:\/\/doi.org\/10.1109\/SFCS.1995.492475","DOI":"10.1109\/SFCS.1995.492475"},{"key":"730_CR24","unstructured":"Poljak, S.: A note on stable sets and colorings of graphs. In: Commentationes Mathematicae Universitatis Carolinae, pp. 307\u2013309 (1974)"},{"issue":"4","key":"730_CR25","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/j.orl.2003.10.009","volume":"32","author":"B Reed","year":"2004","unstructured":"Reed, B., Smith, K., Vetta, A.: Finding odd cycle transversals. Oper. Res. Lett. 32(4), 299\u2013301 (2004)","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"730_CR26","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1093\/comjnl\/bxm038","volume":"51","author":"C Sloper","year":"2008","unstructured":"Sloper, C., Telle, J.A.: An overview of techniques for designing parameterized algorithms. Comput. J. 51(1), 122\u2013136 (2008). https:\/\/doi.org\/10.1093\/comjnl\/bxm038","journal-title":"Comput. J."},{"issue":"3","key":"730_CR27","doi-asserted-by":"publisher","first-page":"619","DOI":"10.1007\/s00453-015-0083-x","volume":"77","author":"S Thomass\u00e9","year":"2017","unstructured":"Thomass\u00e9, S., Trotignon, N., Vuskovic, K.: A polynomial Turing-Kernel for weighted independent set in bull-free graphs. Algorithmica 77(3), 619\u2013641 (2017)","journal-title":"Algorithmica"},{"issue":"1","key":"730_CR28","doi-asserted-by":"publisher","first-page":"103","DOI":"10.4086\/toc.2007.v003a006","volume":"3","author":"D Zuckerman","year":"2007","unstructured":"Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. Theory Comput. 3(1), 103\u2013128 (2007)","journal-title":"Theory Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00730-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-020-00730-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00730-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,17]],"date-time":"2021-06-17T00:04:20Z","timestamp":1623888260000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-020-00730-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,17]]},"references-count":28,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2020,8]]}},"alternative-id":["730"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00730-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,6,17]]},"assertion":[{"value":"21 December 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 June 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 June 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}