{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T05:26:57Z","timestamp":1767245217810,"version":"3.37.3"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2018,7,16]],"date-time":"2018-07-16T00:00:00Z","timestamp":1531699200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100011199","name":"FP7 Ideas: European Research Council","doi-asserted-by":"publisher","award":["280152","280152"],"award-info":[{"award-number":["280152","280152"]}],"id":[{"id":"10.13039\/100011199","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["714704","725978"],"award-info":[{"award-number":["714704","725978"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["725978","715744"],"award-info":[{"award-number":["725978","715744"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"name":"National Research, Development and Innovation Office - NKFIH","award":["SNN 116095"],"award-info":[{"award-number":["SNN 116095"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,2]]},"DOI":"10.1007\/s00453-018-0479-5","type":"journal-article","created":{"date-parts":[[2018,7,16]],"date-time":"2018-07-16T09:44:21Z","timestamp":1531734261000},"page":"421-438","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":16,"title":["Subexponential-Time Algorithms for Maximum Independent Set in \n                \n                  \n                \n                $$P_t$$\n                \n                  \n                    \n                      P\n                      t\n                    \n                  \n                \n              -Free and Broom-Free Graphs"],"prefix":"10.1007","volume":"81","author":[{"given":"G\u00e1bor","family":"Bacs\u00f3","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"D\u00e1niel","family":"Marx","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcin","family":"Pilipczuk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zsolt","family":"Tuza","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Erik Jan","family":"van\u00a0Leeuwen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,7,16]]},"reference":[{"issue":"1\u20133","key":"479_CR1","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0166-218X(03)00386-X","volume":"132","author":"G Agnarsson","year":"2003","unstructured":"Agnarsson, G., Damaschke, P., Halld\u00f3rsson, M.M.: Powers of geometric intersection graphs and dispersion algorithms. Discrete Appl. Math. 132(1\u20133), 3\u201316 (2003)","journal-title":"Discrete Appl. Math."},{"key":"479_CR2","first-page":"3","volume-title":"The Effect of Local Constraints on the Complexity of Determination of the Graph Independence Number. Combinatorial-Algebraic Methods in Applied Mathematics","author":"V Alekseev","year":"1982","unstructured":"Alekseev, V.: The Effect of Local Constraints on the Complexity of Determination of the Graph Independence Number. Combinatorial-Algebraic Methods in Applied Mathematics, pp. 3\u201313. Gorkiy University Press, Gorkiy (1982). (in Russian)"},{"issue":"1\u20133","key":"479_CR3","first-page":"3","volume":"135","author":"VE Alekseev","year":"2004","unstructured":"Alekseev, V.E.: Polynomial algorithm for finding the largest independent sets in graphs without forks. Discrete Appl. Math. 135(1\u20133), 3\u201316 (2004)","journal-title":"Discrete Appl. Math."},{"key":"479_CR4","unstructured":"Bacs\u00f3, G., Marx, D., Tuza, Z.: \n                    \n                      \n                    \n                    $${H}$$\n                    \n                      \n                        H\n                      \n                    \n                  -free graphs, independent sets, and subexponential-time algorithms. In: Guo, J., Hermelin, D. (eds.) 11th International Symposium on Parameterized and Exact Computation, IPEC 2016, August 24\u201326, 2016, Aarhus, Denmark, vol. 63 of LIPIcs, pp. 3:1\u20133:12. Schloss Dagstuhl\u2014Leibniz-Zentrum fuer Informatik (2016)"},{"key":"479_CR5","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/S0166-218X(96)00063-7","volume":"71","author":"V Bafna","year":"1996","unstructured":"Bafna, V., Narayanan, B., Ravi, R.: Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles). Discrete Appl. Math. 71, 41\u201353 (1996)","journal-title":"Discrete Appl. Math."},{"key":"479_CR6","doi-asserted-by":"crossref","unstructured":"Berman, P.: A \n                    \n                      \n                    \n                    $$d\/2$$\n                    \n                      \n                        \n                          d\n                          \/\n                          2\n                        \n                      \n                    \n                   approximation for maximum weight independent set in \n                    \n                      \n                    \n                    $$d$$\n                    \n                      \n                        d\n                      \n                    \n                  -claw free graphs. In: Halld\u00f3rsson, M. (ed.) Algorithm Theory\u2014SWAT 2000, 7th Scandinavian Workshop on Algorithm Theory, Bergen Norway, July 2000, Proceedings, pp. 214\u2013219. Springer (2000)","DOI":"10.1007\/3-540-44985-X_19"},{"key":"479_CR7","unstructured":"Bhattacharya, B.K., Houle, M.E.: Generalized maximum independent sets for trees in subquadratic time. In: Algorithms and Computation, 10th International Symposium, ISAAC \u201999, Chennai, India, December 16\u201318, 1999, Proceedings, pp. 435\u2013445 (1999)"},{"key":"479_CR8","unstructured":"Brandst\u00e4dt, A., Mosca, R.: Maximum weight independent sets for (\n                    \n                      \n                    \n                    $${P}_7$$\n                    \n                      \n                        \n                          P\n                          7\n                        \n                      \n                    \n                  , triangle)-free graphs in polynomial time. CoRR, \n                    arXiv:1511.08066\n                    \n                   (2015)"},{"key":"479_CR9","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/j.dam.2016.06.016","volume":"231","author":"C Brause","year":"2017","unstructured":"Brause, C.: A subexponential-time algorithm for the maximum independent set problem in \n                    \n                      \n                    \n                    $${P}_t$$\n                    \n                      \n                        \n                          P\n                          t\n                        \n                      \n                    \n                  -free graphs. Discrete Appl. Math. 231, 113\u2013118 (2017)","journal-title":"Discrete Appl. Math."},{"key":"479_CR10","unstructured":"Chalermsook, P., Laekhanukit, B., Nanongkai, D.: Independent set, induced matching, and pricing: connections and tight (subexponential time) approximation hardnesses. In: 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26\u201329 October, 2013, Berkeley, CA, USA, pp. 370\u2013379 (2013)"},{"key":"479_CR11","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)"},{"issue":"1","key":"479_CR12","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/s10878-012-9594-4","volume":"27","author":"H Eto","year":"2014","unstructured":"Eto, H., Guo, F., Miyano, E.: Distance-\n                    \n                      \n                    \n                    $$d$$\n                    \n                      \n                        d\n                      \n                    \n                   independent set problems for bipartite and chordal graphs. J. Comb. Optim. 27(1), 88\u201399 (2014)","journal-title":"J. Comb. Optim."},{"key":"479_CR13","volume-title":"Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin (2006)"},{"key":"479_CR14","unstructured":"Grzesik, A., Klimo\u0161ov\u00e1, T., Pilipczuk, M., Pilipczuk, M.: Polynomial-time algorithm for maximum weight independent set on \n                    \n                      \n                    \n                    $${P}_6$$\n                    \n                      \n                        \n                          P\n                          6\n                        \n                      \n                    \n                  -free graphs. CoRR, \n                    arXiv:1707.05491\n                    \n                   (2017)"},{"issue":"3\u20134","key":"479_CR15","first-page":"413","volume":"XIX","author":"A Gy\u00e1rf\u00e1s","year":"1987","unstructured":"Gy\u00e1rf\u00e1s, A.: Problems from the world surrounding perfect graphs. Zastowania Matematyki Appl. Math. XIX(3\u20134), 413\u2013441 (1987)","journal-title":"Zastowania Matematyki Appl. Math."},{"key":"479_CR16","unstructured":"Halld\u00f3rson, M.\u00a0M.: Approximating discrete collections via local improvements. In: Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201995), pp. 160\u2013169. SIAM (1995)"},{"issue":"4","key":"479_CR17","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"479_CR18","first-page":"41","volume":"105","author":"D Lokshtanov","year":"2011","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Lower bounds based on the exponential time hypothesis. Bull. EATCS 105, 41\u201372 (2011)","journal-title":"Bull. EATCS"},{"key":"479_CR19","unstructured":"Lokshtanov, D., Pilipczuk, M., van Leeuwen, E.J.: Independence and efficient domination on \n                    \n                      \n                    \n                    $${P}_{\\text{6}}$$\n                    \n                      \n                        \n                          P\n                          6\n                        \n                      \n                    \n                  -free graphs. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10\u201312, 2016, pp. 1784\u20131803 (2016)"},{"key":"479_CR20","unstructured":"Lokshtanov, D., Vatshelle, M., Villanger, Y.: Independent set in \n                    \n                      \n                    \n                    $${P}_5$$\n                    \n                      \n                        \n                          P\n                          5\n                        \n                      \n                    \n                  -free graphs in polynomial time. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, OR, USA, January 5\u20137, 2014, pp. 570\u2013581 (2014)"},{"issue":"4","key":"479_CR21","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1016\/j.jda.2008.04.001","volume":"6","author":"VV Lozin","year":"2008","unstructured":"Lozin, V.V., Milanic, M.: A polynomial algorithm to find an independent set of maximum weight in a fork-free graph. J. Discrete Algorithms 6(4), 595\u2013604 (2008)","journal-title":"J. Discrete Algorithms"},{"issue":"1","key":"479_CR22","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1016\/j.dam.2004.07.006","volume":"146","author":"VV Lozin","year":"2005","unstructured":"Lozin, V.V., Mosca, R.: Independent sets in extensions of \n                    \n                      \n                    \n                    $$2{K}_2$$\n                    \n                      \n                        \n                          2\n                          \n                            K\n                            2\n                          \n                        \n                      \n                    \n                  -free graphs. Discrete Appl. Math. 146(1), 74\u201380 (2005)","journal-title":"Discrete Appl. Math."},{"key":"479_CR23","unstructured":"Marx, D., Pilipczuk, M.: Optimal parameterized algorithms for planar facility location problems using Voronoi diagrams. In: Algorithms\u2014ESA 2015\u201423rd Annual European Symposium, Patras, Greece, September 14\u201316, 2015, Proceedings, pp. 865\u2013877 (2015)"},{"issue":"3","key":"479_CR24","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"},{"issue":"9","key":"479_CR25","doi-asserted-by":"publisher","first-page":"1041","DOI":"10.1016\/j.dam.2010.01.007","volume":"158","author":"B Randerath","year":"2010","unstructured":"Randerath, B., Schiermeyer, I.: On maximum independent sets in \n                    \n                      \n                    \n                    $${P}_5$$\n                    \n                      \n                        \n                          P\n                          5\n                        \n                      \n                    \n                  -free graphs. Discrete Appl. Math. 158(9), 1041\u20131044 (2010)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"479_CR26","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1023\/A:1009802105661","volume":"4","author":"DJ Rosenkrantz","year":"2000","unstructured":"Rosenkrantz, D.J., Tayi, G.K., Ravi, S.S.: Facility dispersion problems under capacity and cost constraints. J. Comb. Optim. 4(1), 7\u201333 (2000)","journal-title":"J. Comb. Optim."},{"issue":"1","key":"479_CR27","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0012-365X(90)90287-R","volume":"29","author":"N Sbihi","year":"1980","unstructured":"Sbihi, N.: Algorithme de recherche d\u2019un stable de cardinalite maximum dans un graphe sans etoile. Discrete Math. 29(1), 53\u201376 (1980)","journal-title":"Discrete Math."},{"key":"479_CR28","unstructured":"Thilikos, D.M.: Fast sub-exponential algorithms and compactness in planar graphs. In: Algorithms\u2014ESA 2011\u201419th Annual European Symposium, Saarbr\u00fccken, Germany, September 5\u20139, 2011. Proceedings, pp. 358\u2013369 (2011)"},{"key":"479_CR29","doi-asserted-by":"publisher","first-page":"737","DOI":"10.1002\/(SICI)1520-6750(199608)43:5<737::AID-NAV9>3.0.CO;2-6","volume":"43","author":"G Yu","year":"1996","unstructured":"Yu, G., Goldschmidt, O.: On locally optimal independent sets and vertex covers. Naval Res. Logistics 43, 737\u2013748 (1996)","journal-title":"Naval Res. Logistics"},{"issue":"1","key":"479_CR30","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":"http:\/\/link.springer.com\/article\/10.1007\/s00453-018-0479-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0479-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0479-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,20]],"date-time":"2019-09-20T10:37:52Z","timestamp":1568975872000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-018-0479-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7,16]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,2]]}},"alternative-id":["479"],"URL":"https:\/\/doi.org\/10.1007\/s00453-018-0479-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2018,7,16]]},"assertion":[{"value":"18 November 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 July 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 July 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}