{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T18:10:39Z","timestamp":1774635039299,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642041273","type":"print"},{"value":"9783642041280","type":"electronic"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-04128-0_57","type":"book-chapter","created":{"date-parts":[[2009,9,14]],"date-time":"2009-09-14T14:16:36Z","timestamp":1252937796000},"page":"635-646","source":"Crossref","is-referenced-by-count":25,"title":["Kernel Bounds for Disjoint Cycles and Disjoint Paths"],"prefix":"10.1007","author":[{"given":"Hans L.","family":"Bodlaender","sequence":"first","affiliation":[]},{"given":"St\u00e9phan","family":"Thomass\u00e9","sequence":"additional","affiliation":[]},{"given":"Anders","family":"Yeo","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"57_CR1","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/s003730200002","volume":"18","author":"N. Alon","year":"2002","unstructured":"Alon, N., Hoory, S., Linial, N.: The Moore bound for irregular graphs. Graphs and Combinatorics\u00a018, 53\u201357 (2002)","journal-title":"Graphs and Combinatorics"},{"key":"57_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1007\/978-3-540-70918-3_28","volume-title":"STACS 2007","author":"H.L. Bodlaender","year":"2007","unstructured":"Bodlaender, H.L.: A cubic kernel for feedback vertex set. In: Thomas, W., Weil, P. (eds.) STACS 2007. LNCS, vol.\u00a04393, pp. 320\u2013331. Springer, Heidelberg (2007)"},{"key":"57_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1007\/978-3-540-70575-8_46","volume-title":"Automata, Languages and Programming","author":"H.L. Bodlaender","year":"2008","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels (extended abstract). In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol.\u00a05125, pp. 563\u2013574. Springer, Heidelberg (2008)"},{"key":"57_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1007\/978-3-540-79723-4_16","volume-title":"Parameterized and Exact Computation","author":"H.L. Bodlaender","year":"2008","unstructured":"Bodlaender, H.L., Penninkx, E.: A linear kernel for planar feedback vertex set. In: Grohe, M., Niedermeier, R. (eds.) IWPEC 2008. LNCS, vol.\u00a05018, pp. 160\u2013171. Springer, Heidelberg (2008)"},{"key":"57_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1007\/978-3-540-92182-0_29","volume-title":"Algorithms and Computation","author":"H.L. Bodlaender","year":"2008","unstructured":"Bodlaender, H.L., Penninkx, E., Tan, R.B.: A linear kernel for the k-disjoint cycle problem on planar graphs. In: Hong, S.-H., Nagamochi, H., Fukunaga, T. (eds.) ISAAC 2008. LNCS, vol.\u00a05369, pp. 306\u2013317. Springer, Heidelberg (2008)"},{"key":"57_CR6","unstructured":"Bodlaender, H.L., Thomass\u00e9, S., Yeo, A.: Analysis of data reduction: Transformations give evidence for non-existence of polynomial kernels. Technical Report CS-UU-2008-030, Department of Information and Computer Sciences, Utrecht University, Utrecht, The Netherlands (2008)"},{"key":"57_CR7","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/S0168-0072(95)00020-8","volume":"84","author":"L. Cai","year":"1997","unstructured":"Cai, L., Chen, J., Downey, R.G., Fellows, M.R.: Advice classes of parameterized tractability. Annals of Pure and Applied Logic\u00a084, 119\u2013138 (1997)","journal-title":"Annals of Pure and Applied Logic"},{"key":"57_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"378","DOI":"10.1007\/978-3-642-02927-1_32","volume-title":"ICALP 2009. Part I","author":"M. Dom","year":"2009","unstructured":"Dom, M., Lokshtanov, D., Saurabh, S.: Incompressibility through colors and IDs. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009. Part I. LNCS, vol.\u00a05555, pp. 378\u2013389. Springer, Heidelberg (2009)"},{"key":"57_CR9","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1137\/S0097539792228228","volume":"24","author":"R.G. Downey","year":"1995","unstructured":"Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness I: Basic results. SIAM J. Comput.\u00a024, 873\u2013921 (1995)","journal-title":"SIAM J. Comput."},{"key":"57_CR10","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0304-3975(94)00097-3","volume":"141","author":"R.G. Downey","year":"1995","unstructured":"Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness II: On completeness for W[1]. Theor. Comp. Sc.\u00a0141, 109\u2013131 (1995)","journal-title":"Theor. Comp. Sc."},{"key":"57_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)"},{"key":"57_CR12","first-page":"421","volume-title":"Proceedings 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009","author":"H. Fernau","year":"2009","unstructured":"Fernau, H., Fomin, F.V., Lokshtanov, D., Raible, D., Saurabh, S., Villanger, Y.: Kernel(s) for problems with no kernel: On out-trees with many leaves. In: Albers, S., Marion, J.-Y. (eds.) Proceedings 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009, pp. 421\u2013432. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany (2009)"},{"key":"57_CR13","first-page":"133","volume-title":"Proceedings of the 40th Annual Symposium on Theory of Computing, STOC 2008","author":"L. Fortnow","year":"2008","unstructured":"Fortnow, L., Santhanam, R.: Infeasibility of instance compression and succinct PCPs for NP. In: Proceedings of the 40th Annual Symposium on Theory of Computing, STOC 2008, pp. 133\u2013142. ACM Press, New York (2008)"},{"key":"57_CR14","volume-title":"Computers and Intractability, A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability, A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York (1979)"},{"key":"57_CR15","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/1233481.1233493","volume":"38","author":"J. Guo","year":"2007","unstructured":"Guo, J., Niedermeier, R.: Invitation to data reduction and problem kernelization. ACM SIGACT News\u00a038, 31\u201345 (2007)","journal-title":"ACM SIGACT News"},{"key":"57_CR16","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1002\/net.1975.5.1.45","volume":"5","author":"R.M. Karp","year":"1975","unstructured":"Karp, R.M.: On the complexity of combinatorial problems. Networks\u00a05, 45\u201368 (1975)","journal-title":"Networks"},{"key":"57_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"282","DOI":"10.1007\/3-540-36379-3_25","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"T. Kloks","year":"2002","unstructured":"Kloks, T., Lee, C.M., Liu, J.: New algorithms for k-face cover, k-feedback vertex set, and k-disjoint cycles on plane and planar graphs. In: Ku\u010dera, L. (ed.) WG 2002. LNCS, vol.\u00a02573, pp. 282\u2013295. Springer, Heidelberg (2002)"},{"key":"57_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/978-3-540-28639-4_12","volume-title":"Parameterized and Exact Computation","author":"L. Mathieson","year":"2004","unstructured":"Mathieson, L., Prieto, E., Shaw, P.: Packing edge disjoint triangles: A parameterized view. In: Downey, R.G., Fellows, M.R., Dehne, F. (eds.) IWPEC 2004. LNCS, vol.\u00a03162, pp. 127\u2013137. Springer, Heidelberg (2004)"},{"key":"57_CR19","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1006\/jctb.1995.1006","volume":"63","author":"N. Robertson","year":"1995","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XIII. The disjoint paths problem. J. Comb. Theory Series B\u00a063, 65\u2013110 (1995)","journal-title":"J. Comb. Theory Series B"},{"key":"57_CR20","unstructured":"Saurabh, S.: Personal communication (2009)"},{"key":"57_CR21","doi-asserted-by":"crossref","unstructured":"Thomass\u00e9, S.: A quadratic kernel for feedback vertex set. In: Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, pp. 115\u2013119 (2009)","DOI":"10.1137\/1.9781611973068.13"}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA 2009"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-04128-0_57","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,22]],"date-time":"2019-05-22T11:22:08Z","timestamp":1558524128000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-04128-0_57"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642041273","9783642041280"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-04128-0_57","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009]]}}}