{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,17]],"date-time":"2026-01-17T22:25:34Z","timestamp":1768688734429,"version":"3.49.0"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2015,11,16]],"date-time":"2015-11-16T00:00:00Z","timestamp":1447632000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council (GB)","doi-asserted-by":"publisher","award":["EP\/K016423\/1"],"award-info":[{"award-number":["EP\/K016423\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,3]]},"DOI":"10.1007\/s00453-015-0083-x","type":"journal-article","created":{"date-parts":[[2015,11,16]],"date-time":"2015-11-16T14:51:23Z","timestamp":1447685483000},"page":"619-641","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":21,"title":["A Polynomial Turing-Kernel for Weighted Independent Set in Bull-Free Graphs"],"prefix":"10.1007","volume":"77","author":[{"given":"St\u00e9phan","family":"Thomass\u00e9","sequence":"first","affiliation":[]},{"given":"Nicolas","family":"Trotignon","sequence":"additional","affiliation":[]},{"given":"Kristina","family":"Vu\u0161kovi\u0107","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,11,16]]},"reference":[{"key":"83_CR1","doi-asserted-by":"crossref","DOI":"10.1002\/9780470277331","volume-title":"The Probabilistic Method","author":"N Alon","year":"2008","unstructured":"Alon, N., Spencer, J.H.: The Probabilistic Method. Wiley, London (2008)"},{"issue":"8","key":"83_CR2","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1016\/j.jcss.2009.04.001","volume":"75","author":"H Bodlaender","year":"2009","unstructured":"Bodlaender, H., Downey, R., Fellows, M., Hermelin, D.: On problems without polynomial kernels. J. Comput. Syst. Sci. 75(8), 423\u2013434 (2009)","journal-title":"J. Comput. Syst. Sci."},{"key":"83_CR3","unstructured":"Brandst\u00e4dt, A., Mosca, R.: Maximum weight independent sets in odd-hole-free graphs without dart or without bull. CoRR, abs\/1209.2512 (2012)"},{"issue":"1","key":"83_CR4","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1016\/j.jctb.2011.07.003","volume":"102","author":"M Chudnovsky","year":"2012","unstructured":"Chudnovsky, M.: The structure of bull-free graphs I: three-edge-paths with center and anticenters. J. Comb. Theory B 102(1), 233\u2013251 (2012)","journal-title":"J. Comb. Theory B"},{"issue":"1","key":"83_CR5","doi-asserted-by":"crossref","first-page":"252","DOI":"10.1016\/j.jctb.2011.07.002","volume":"102","author":"M Chudnovsky","year":"2012","unstructured":"Chudnovsky, M.: The structure of bull-free graphs II and III: a summary. J. Comb. Theory B 102(1), 252\u2013282 (2012)","journal-title":"J. Comb. Theory B"},{"key":"83_CR6","unstructured":"Chudnovsky, M.: The structure of bull-free graphs II: elementary trigraphs. https:\/\/web.math.princeton.edu\/~mchudnov\/bulls2.pdf"},{"key":"83_CR7","unstructured":"Chudnovsky, M.: The structure of bull-free graphs III: global structure. https:\/\/web.math.princeton.edu\/~mchudnov\/bulls3.pdf"},{"issue":"2","key":"83_CR8","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1007\/s00493-005-0012-8","volume":"25","author":"M Chudnovsky","year":"2005","unstructured":"Chudnovsky, M., Cornu\u00e9jols, G., Liu, X., Seymour, P., Vu\u0161kovi\u0107, K.: Recognizing berge graphs. Combinatorica 25(2), 143\u2013186 (2005)","journal-title":"Combinatorica"},{"issue":"1","key":"83_CR9","doi-asserted-by":"crossref","first-page":"51","DOI":"10.4007\/annals.2006.164.51","volume":"164","author":"M Chudnovsky","year":"2006","unstructured":"Chudnovsky, M., Robertson, N., Seymour, P., Thomas, R.: The strong perfect graph theorem. Ann. Math. 164(1), 51\u2013229 (2006)","journal-title":"Ann. Math."},{"key":"83_CR10","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/j.jda.2011.12.012","volume":"14","author":"K Dabrowski","year":"2012","unstructured":"Dabrowski, K., Lozin, 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":"83_CR11","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity, Monographs in Computer Science","author":"RG Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity, Monographs in Computer Science. Springer, New York (1999)"},{"key":"83_CR12","doi-asserted-by":"crossref","unstructured":"Faenza, Y., Oriolo, G., Stauffer, G.: An algorithmic decomposition of claw-free graphs leading to an $$O(n^{3}$$ O ( n 3 )-algorithm for the weighted stable set problem. In: SODA, pp. 630\u2013646 (2011)","DOI":"10.1137\/1.9781611973082.49"},{"key":"83_CR13","doi-asserted-by":"crossref","unstructured":"Farrugia, A.: Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard. Electron. J. Combin. 11(1), R46 (2004)","DOI":"10.37236\/1799"},{"key":"83_CR14","unstructured":"Fernau, H., Fomin, F., Lokshtanov, D., Raible, D., Saurabh, S., Villanger, Y.: Kernels for Problems with No Kernel: On Out-Trees with Many Leaves. STACS, Freiburg (2009)"},{"key":"83_CR15","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-97881-4","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"M Gr\u00f6tschel","year":"1988","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer, Berlin (1988)"},{"key":"83_CR16","first-page":"413","volume":"19","author":"A Gy\u00e1rf\u00e1s","year":"1987","unstructured":"Gy\u00e1rf\u00e1s, A.: Problems from the world surrounding perfect graphs. Zastowania Mat. Appl. Math. 19, 413\u2013441 (1987)","journal-title":"Zastowania Mat. Appl. Math."},{"key":"83_CR17","doi-asserted-by":"crossref","unstructured":"Habib, M., Mamcarz, A., de\u00a0Montgolfier, F.: Algorithms for some $$H$$ H -join decompositions. In: Fern\u00e1ndez-Baca [17], pp. 446\u2013457","DOI":"10.1007\/978-3-642-29344-3_38"},{"issue":"1","key":"83_CR18","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/j.cosrev.2010.01.001","volume":"4","author":"M Habib","year":"2010","unstructured":"Habib, M., Paul, C.: A survey of the algorithmic aspects of modular decomposition. Comput. Sci. Rev. 4(1), 41\u201359 (2010)","journal-title":"Comput. Sci. Rev."},{"key":"83_CR19","doi-asserted-by":"crossref","unstructured":"Hermelin, D., Kratsch, S., Soltys, K., Wahlstr\u00f6m, M., Wu, X.: A Completeness Theory for Polynomial (Turing) Kernelization. IPEC (2013)","DOI":"10.1007\/978-3-319-03898-8_18"},{"key":"83_CR20","doi-asserted-by":"crossref","unstructured":"Jansen, B.M.P.: Turing kernelization for finding long paths and cycles in restricted graph classes. CoRR, abs\/1402.4718 (2014)","DOI":"10.1007\/978-3-662-44777-2_48"},{"key":"83_CR21","unstructured":"Lokshtanov, D.: New Methods in Parameterized Algorithms and Complexity. PhD thesis, University of Bergen (2009)"},{"key":"83_CR22","unstructured":"Lokshtantov, D., Vatshelle, M., Villanger, Y.: Independent set in $$p_5$$ p 5 -free graphs in polynomial time. SODA 2014, 570\u2013581 (2013)"},{"key":"83_CR23","doi-asserted-by":"crossref","unstructured":"Makino, K., Uno, T.: New algorithms for enumerating all maximal cliques. In: Hagerup and Katajainen [23], pp. 260\u2013272","DOI":"10.1007\/978-3-540-27810-8_23"},{"key":"83_CR24","first-page":"307","volume":"15","author":"S Poljak","year":"1974","unstructured":"Poljak, S.: A note on the stable sets and coloring of graphs. Comment. Math. Univ. Carol. 15, 307\u2013309 (1974)","journal-title":"Comment. Math. Univ. Carol."},{"key":"83_CR25","doi-asserted-by":"crossref","first-page":"370","DOI":"10.2307\/2041460","volume":"64","author":"V R\u00f6dl","year":"1976","unstructured":"R\u00f6dl, V.: On the chromatic number of subgraphs of a given graph. Proc. Am. Math. Soc. 64, 370\u2013371 (1976)","journal-title":"Proc. Am. Math. Soc."},{"key":"83_CR26","unstructured":"Perret du Cray, H., Sau, I.: Improved FPT algorithms for weighted independent set in bull-free graphs. arXiv:1407.1706"},{"issue":"1","key":"83_CR27","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/0097-3165(72)90019-2","volume":"13","author":"N Sauer","year":"1972","unstructured":"Sauer, N.: On the density of families of sets. J. Comb. Theory Ser. A 13(1), 145\u2013147 (1972)","journal-title":"J. Comb. Theory Ser. A"},{"key":"83_CR28","doi-asserted-by":"crossref","unstructured":"Thomass\u00e9, S., Trotignon, N., Vu\u0161kovi\u0107, K.: A polynomial Turing-kernel for weighted independent set in bull-free graphs. In: Kratsch and Todinca [26], pp. 408\u2013419","DOI":"10.1007\/978-3-319-12340-0_34"},{"issue":"3","key":"83_CR29","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1137\/0206036","volume":"6","author":"S Tsukiyama","year":"1977","unstructured":"Tsukiyama, S., Ide, M., Ariyoshi, H., Shirakawa, I.: A new algorithm for generating all the maximal independent sets. SIAM J. Comput. 6(3), 505\u2013517 (1977)","journal-title":"SIAM J. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0083-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-015-0083-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0083-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0083-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,11]],"date-time":"2020-09-11T12:05:22Z","timestamp":1599825922000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-015-0083-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,11,16]]},"references-count":29,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,3]]}},"alternative-id":["83"],"URL":"https:\/\/doi.org\/10.1007\/s00453-015-0083-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,11,16]]}}}