{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:27:50Z","timestamp":1761611270866},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540230250"},{"type":"electronic","value":"9783540301400"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-30140-0_56","type":"book-chapter","created":{"date-parts":[[2010,9,19]],"date-time":"2010-09-19T01:31:13Z","timestamp":1284859873000},"page":"628-639","source":"Crossref","is-referenced-by-count":11,"title":["Contraction and Treewidth Lower Bounds"],"prefix":"10.1007","author":[{"given":"Hans L.","family":"Bodlaender","sequence":"first","affiliation":[]},{"given":"Arie M. C. A.","family":"Koster","sequence":"additional","affiliation":[]},{"given":"Thomas","family":"Wolle","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"56_CR1","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, 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"key":"56_CR2","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. Comp. Sc.\u00a0209, 1\u201345 (1998)","journal-title":"Theor. Comp. Sc."},{"key":"56_CR3","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Koster, A.M.C.A.: On the maximum cardinality search lower bound for treewidth (2004), Extended abstract to appear in proceedings WG 2004","DOI":"10.1007\/978-3-540-30559-0_7"},{"key":"56_CR4","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":"56_CR5","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B. Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic of graphs I: Recognizable sets of finite graphs. Information and Computation\u00a085, 12\u201375 (1990)","journal-title":"Information and Computation"},{"key":"56_CR6","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1998","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1998)"},{"key":"56_CR7","unstructured":"Gogate, V., Dechter, R.: A complete anytime algorithm for treewidth. In: To appear in Proceedings UAI 2004, Uncertainty in Artificial Intelligence (2004)"},{"key":"56_CR8","unstructured":"Koster, A.M.C.A.: Frequency assignment - Models and Algorithms. PhD thesis, Univ. Maastricht, Maastricht, the Netherlands (1999)"},{"key":"56_CR9","volume-title":"Electronic Notes in Discrete Mathematics","author":"A.M.C.A. Koster","year":"2001","unstructured":"Koster, A.M.C.A., Bodlaender, H.L., van Hoesel, S.P.M.: Treewidth: Computational experiments. In: Broersma, H., Faigle, U., Hurink, J., Pickl, S. (eds.) Electronic Notes in Discrete Mathematics, vol.\u00a08, Elsevier Science Publishers, Amsterdam (2001)"},{"key":"56_CR10","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1002\/net.10046","volume":"40","author":"A.M.C.A. Koster","year":"2002","unstructured":"Koster, A.M.C.A., van Hoesel, S.P.M., Kolen, A.W.J.: Solving partial constraint satisfaction problems with tree decomposition. Networks\u00a040, 170\u2013180 (2002)","journal-title":"Networks"},{"key":"56_CR11","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1111\/j.2517-6161.1988.tb01721.x","volume":"50","author":"S.J. Lauritzen","year":"1988","unstructured":"Lauritzen, S.J., Spiegelhalter, D.J.: Local computations with probabilities on graphical structures and their application to expert systems. The Journal of the Royal Statistical Society. Series B (Methodological)\u00a050, 157\u2013224 (1988)","journal-title":"The Journal of the Royal Statistical Society. Series B (Methodological)"},{"key":"56_CR12","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1137\/S0895480101397773","volume":"16","author":"B. Lucena","year":"2003","unstructured":"Lucena, B.: A new lower bound for tree-width using maximum cardinality search. SIAM J. Disc. Math.\u00a016, 345\u2013353 (2003)","journal-title":"SIAM J. Disc. Math."},{"key":"56_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1007\/3-540-59071-4_34","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"S. Ramachandramurthi","year":"1995","unstructured":"Ramachandramurthi, S.: A lower bound for treewidth and its consequences. In: Mayr, E.W., Schmidt, G., Tinhofer, G. (eds.) WG 1994. LNCS, vol.\u00a0903, pp. 14\u201325. Springer, Heidelberg (1995)"},{"key":"56_CR14","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/S0895480195280010","volume":"10","author":"S. Ramachandramurthi","year":"1997","unstructured":"Ramachandramurthi, S.: The structure and number of obstructions to treewidth. SIAM J. Disc. Math.\u00a010, 146\u2013157 (1997)","journal-title":"SIAM J. Disc. Math."},{"key":"56_CR15","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XX. Wagner\u2019s conjecture (to appear)"},{"key":"56_CR16","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":"56_CR17","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1006\/jctb.1994.1073","volume":"62","author":"N. Robertson","year":"1994","unstructured":"Robertson, N., Seymour, P.D., Thomas, R.: Quickly excluding a planar graph. J. Comb. Theory Series B\u00a062, 323\u2013348 (1994)","journal-title":"J. Comb. Theory Series B"},{"key":"56_CR18","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1137\/0213035","volume":"13","author":"R.E. Tarjan","year":"1984","unstructured":"Tarjan, R.E., Yannakakis, M.: Simple linear time algorithms to test chordiality of graphs, test acyclicity of graphs, and selectively reduce acyclic hypergraphs. SIAM J. Comput.\u00a013, 566\u2013579 (1984)","journal-title":"SIAM J. Comput."},{"key":"56_CR19","unstructured":"Treewidthlib, http:\/\/www.cs.uu.nl\/people\/hansb\/treewidthlib , 2004-03-31"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2004"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-30140-0_56.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T04:44:40Z","timestamp":1605761080000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-30140-0_56"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540230250","9783540301400"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-30140-0_56","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}