{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:55:41Z","timestamp":1725558941061},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540241324"},{"type":"electronic","value":"9783540305590"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-30559-0_7","type":"book-chapter","created":{"date-parts":[[2010,7,2]],"date-time":"2010-07-02T19:01:42Z","timestamp":1278097302000},"page":"81-92","source":"Crossref","is-referenced-by-count":7,"title":["On the Maximum Cardinality Search Lower Bound for Treewidth"],"prefix":"10.1007","author":[{"given":"Hans L.","family":"Bodlaender","sequence":"first","affiliation":[]},{"given":"Arie M. C. A.","family":"Koster","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"7_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":"7_CR2","unstructured":"Bodlaender, H.L., Koster, A.M.C.A.: Safe separators for treewidth. In: Proceedings 6th Workshop on Algorithm Engineering and Experiments ALENEX 2004, pp. 70\u201378 (2004)"},{"key":"7_CR3","first-page":"32","volume-title":"Proceedings of the 17th Conference on Uncertainty in Artificial Intelligence","author":"H.L. Bodlaender","year":"2001","unstructured":"Bodlaender, H.L., Koster, A.M.C.A., van den Eijkhof, F., van der Gaag, L.C.: Pre-processing for triangulation of probabilistic networks. In: Breese, J., Koller, D. (eds.) Proceedings of the 17th Conference on Uncertainty in Artificial Intelligence, pp. 32\u201339. Morgan Kaufmann, San Francisco (2001)"},{"key":"7_CR4","doi-asserted-by":"crossref","first-page":"628","DOI":"10.1007\/978-3-540-30140-0_56","volume-title":"Algorithms \u2013 ESA 2004","author":"Hans L. Bodlaender","year":"2004","unstructured":"Bodlaender, H.L., Koster, A.M.C.A., Wolle, T.: Contraction and treewidth lower bounds. Technical report UU-CS-2004-034, Institute of Information and Computing Sciences, Utrecht University (2004); To appear in proceedings ESA 2004"},{"key":"7_CR5","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":"7_CR6","unstructured":"Gogate, V., Dechter, R.: A complete anytime algorithm for treewidth. To appear in proceedings UAI 2004, Uncertainty in Artificial Intelligence (2004)"},{"key":"7_CR7","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":"7_CR8","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":"7_CR9","first-page":"157","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"},{"key":"7_CR10","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":"7_CR11","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":"7_CR12","unstructured":"R\u00f6hrig, H.: Tree decomposition: A feasibility study. Master\u2019s thesis, Max-Planck- Institut f\u00fcr Informatik, Saarbr\u00fccken, Germany (1998)"},{"key":"7_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0021-9800(68)80081-X","volume":"4","author":"G. Szekeres","year":"1968","unstructured":"Szekeres, G., Wilf, H.S.: An inequality for the chromatic number of a graph. J. Comb. Theory\u00a04, 1\u20133 (1968)","journal-title":"J. Comb. Theory"},{"key":"7_CR14","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":"7_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1007\/3-540-36379-3_16","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"F. Eijkhof van den","year":"2002","unstructured":"van den Eijkhof, F., Bodlaender, H.L.: Safe reduction rules for weighted treewidth. In: Ku\u010dera, L. (ed.) WG 2002. LNCS, vol.\u00a02573, pp. 176\u2013185. Springer, Heidelberg (2002)"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-30559-0_7.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,3]],"date-time":"2021-05-03T03:30:04Z","timestamp":1620012604000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-30559-0_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540241324","9783540305590"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-30559-0_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}