{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,14]],"date-time":"2026-01-14T23:35:31Z","timestamp":1768433731379,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642311543","type":"print"},{"value":"9783642311550","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-31155-0_31","type":"book-chapter","created":{"date-parts":[[2012,6,13]],"date-time":"2012-06-13T02:21:27Z","timestamp":1339554087000},"page":"352-363","source":"Crossref","is-referenced-by-count":11,"title":["Kernel Bounds for Structural Parameterizations of Pathwidth"],"prefix":"10.1007","author":[{"given":"Hans L.","family":"Bodlaender","sequence":"first","affiliation":[]},{"given":"Bart M. P.","family":"Jansen","sequence":"additional","affiliation":[]},{"given":"Stefan","family":"Kratsch","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"31_CR1","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. SIGACT News\u00a038(1), 31\u201345 (2007)","journal-title":"SIGACT News"},{"key":"31_CR2","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/0095-8956(83)90079-5","volume":"35","author":"N. Robertson","year":"1983","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. I. Excluding a forest. J. Comb. Theory, Ser. B\u00a035, 39\u201361 (1983)","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"1-2","key":"31_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","volume":"209","author":"H.L. Bodlaender","year":"1998","unstructured":"Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theor. Comput. Sci.\u00a0209(1-2), 1\u201345 (1998)","journal-title":"Theor. Comput. Sci."},{"key":"31_CR4","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S. Arnborg","year":"1987","unstructured":"Arnborg, S., Corneil, D.G., Proskurowski, A.: Complexity of finding embeddings in a k-tree. SIAM Journal on Algebraic and Discrete Methods\u00a08, 277\u2013284 (1987)","journal-title":"SIAM Journal on Algebraic and Discrete Methods"},{"key":"31_CR5","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/0166-218X(93)90012-D","volume":"45","author":"J. Gustedt","year":"1993","unstructured":"Gustedt, J.: On the pathwidth of chordal graphs. Discrete Appl. Math.\u00a045, 233\u2013248 (1993)","journal-title":"Discrete Appl. Math."},{"key":"31_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1007\/978-3-642-22006-7_37","volume-title":"Automata, Languages and Programming","author":"H.L. Bodlaender","year":"2011","unstructured":"Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part I. LNCS, vol.\u00a06755, pp. 437\u2013448. Springer, Heidelberg (2011)"},{"issue":"2","key":"31_CR7","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/s00453-006-1226-x","volume":"47","author":"F. Eijkhof van den","year":"2007","unstructured":"van den Eijkhof, F., Bodlaender, H.L., Koster, A.M.C.A.: Safe reduction rules for weighted treewidth. Algorithmica\u00a047(2), 139\u2013158 (2007)","journal-title":"Algorithmica"},{"issue":"3","key":"31_CR8","doi-asserted-by":"publisher","first-page":"286","DOI":"10.1111\/j.1467-8640.2005.00274.x","volume":"21","author":"H.L. Bodlaender","year":"2005","unstructured":"Bodlaender, H.L., Koster, A.M.C.A., van den Eijkhof, F.: Preprocessing rules for triangulation of probabilistic networks. Computational Intelligence\u00a021(3), 286\u2013305 (2005)","journal-title":"Computational Intelligence"},{"issue":"8","key":"31_CR9","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1016\/j.jcss.2009.04.001","volume":"75","author":"H.L. Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. J. Comput. Syst. Sci.\u00a075(8), 423\u2013434 (2009)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"31_CR10","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1006\/inco.1994.1064","volume":"113","author":"J.A. Ellis","year":"1994","unstructured":"Ellis, J.A., Sudborough, I.H., Turner, J.S.: The vertex separation and search number of a graph. Inf. Comput.\u00a0113(1), 50\u201379 (1994)","journal-title":"Inf. Comput."},{"key":"31_CR11","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1137\/0406014","volume":"6","author":"H.L. Bodlaender","year":"1993","unstructured":"Bodlaender, H.L., M\u00f6hring, R.H.: The pathwidth and treewidth of cographs. SIAM J. Discrete Math.\u00a06, 181\u2013188 (1993)","journal-title":"SIAM J. Discrete Math."},{"issue":"3","key":"31_CR12","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1016\/0166-218X(95)00095-9","volume":"64","author":"R.H. M\u00f6hring","year":"1996","unstructured":"M\u00f6hring, R.H.: Triangulating graphs without asteroidal triples. Discrete Applied Mathematics\u00a064(3), 281\u2013287 (1996)","journal-title":"Discrete Applied Mathematics"},{"issue":"6","key":"31_CR13","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H.L. Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput.\u00a025(6), 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"key":"31_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1007\/3-540-44867-5_6","volume-title":"Experimental and Efficient Algorithms","author":"F. Clautiaux","year":"2003","unstructured":"Clautiaux, F., Carlier, J., Moukrim, A., N\u00e9gre, S.: New Lower and Upper Bounds for Graph Treewidth. In: Jansen, K., Margraf, M., Mastrolli, M., Rolim, J.D.P. (eds.) WEA 2003. LNCS, vol.\u00a02647, pp. 70\u201380. Springer, Heidelberg (2003)"},{"key":"31_CR15","unstructured":"Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Cross-composition: A new technique for kernelization lower bounds. In: Proc. 28th STACS, pp. 165\u2013176 (2011)"},{"key":"31_CR16","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/0304-3975(88)90028-X","volume":"58","author":"B. Monien","year":"1988","unstructured":"Monien, B., Sudborough, I.H.: Min cut is NP-complete for edge weighted trees. Theor. Comput. Sci.\u00a058, 209\u2013229 (1988)","journal-title":"Theor. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2013 SWAT 2012"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-31155-0_31.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T11:48:37Z","timestamp":1620128917000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-31155-0_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642311543","9783642311550"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31155-0_31","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012]]}}}