{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T18:04:41Z","timestamp":1725559481382},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540259206"},{"type":"electronic","value":"9783540320784"}],"license":[{"start":{"date-parts":[[2005,1,1]],"date-time":"2005-01-01T00:00:00Z","timestamp":1104537600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11427186_11","type":"book-chapter","created":{"date-parts":[[2010,7,13]],"date-time":"2010-07-13T21:38:24Z","timestamp":1279057104000},"page":"101-112","source":"Crossref","is-referenced-by-count":7,"title":["Degree-Based Treewidth Lower Bounds"],"prefix":"10.1007","author":[{"given":"Arie M. C. A.","family":"Koster","sequence":"first","affiliation":[]},{"given":"Thomas","family":"Wolle","sequence":"additional","affiliation":[]},{"given":"Hans L.","family":"Bodlaender","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"11_CR1","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 J. Alg. Disc. Meth.\u00a08, 277\u2013284 (1987)","journal-title":"SIAM J. Alg. Disc. Meth."},{"key":"11_CR2","volume-title":"Graphs and Digraphs","author":"M. Behzad","year":"1979","unstructured":"Behzad, M., Chartrand, G., Lesniak-Foster, L.: Graphs and Digraphs. Pindle, Weber & Schmidt, Boston (1979)"},{"key":"11_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. Comp. Sc.\u00a0209, 1\u201345 (1998)","journal-title":"Theor. Comp. Sc."},{"key":"11_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/978-3-540-30559-0_7","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"H.L. Bodlaender","year":"2004","unstructured":"Bodlaender, H.L., Koster, A.M.C.A.: On the Maximum Cardinality Search lower bound for treewidth. In: Hromkovi\u010d, J., Nagl, M., Westfechtel, B. (eds.) WG 2004. LNCS, vol.\u00a03353, pp. 81\u201392. Springer, Heidelberg (2004)"},{"key":"11_CR5","unstructured":"Bodlaender, H.L., Koster, A.M.C.A.: Safe separators for treewidth. In: Proceedings 6th Workshop on Algorithm Engineering and Experiments ALENEX2004, pp. 70\u201378 (2004)"},{"key":"11_CR6","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., Eijkhof, F.v.d., 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":"11_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"628","DOI":"10.1007\/978-3-540-30140-0_56","volume-title":"Algorithms \u2013 ESA 2004","author":"H.L. Bodlaender","year":"2004","unstructured":"Bodlaender, H.L., Koster, A.M.C.A., Wolle, T.: Contraction and treewidth lower bounds. In: Albers, S., Radzik, T. (eds.) ESA 2004. LNCS, vol.\u00a03221, pp. 628\u2013639. Springer, Heidelberg (2004)"},{"key":"11_CR8","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Koster, A.M.C.A., Wolle, T.: Contraction and treewidth lower bounds. Technical Report UU-CS-2004-34, Dept. of Computer Science, Utrecht University, Utrecht, The Netherlands (2004)","DOI":"10.1007\/978-3-540-30140-0_56"},{"key":"11_CR9","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1051\/ro:2004011","volume":"38","author":"F. Clautiaux","year":"2004","unstructured":"Clautiaux, F., Moukrim, S.N.A., Carlier, J.: Heuristic and meta-heuristic methods for computing graph treewidth. RAIRO Oper. Res.\u00a038, 13\u201326 (2004)","journal-title":"RAIRO Oper. Res."},{"key":"11_CR10","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":"11_CR11","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.v.d. Eijkhof","year":"2002","unstructured":"Eijkhof, F.v.d., 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)"},{"key":"11_CR12","unstructured":"Gogate, V., Dechter, R.: A complete anytime algorithm for treewidth. In: proceedings UAI 2004. Uncertainty in Artificial Intelligence (2004)"},{"key":"11_CR13","doi-asserted-by":"crossref","unstructured":"Hicks, I.V.: Planar branch decompositions I: The ratcatcher. INFORMS Journal on Computing (2005) (to appear)","DOI":"10.1287\/ijoc.1040.0075"},{"key":"11_CR14","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":"11_CR15","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":"11_CR16","unstructured":"Koster, A.M.C.A., Wolle, T., Bodlaender, H.L.: Degree-based treewidth lower bounds. Technical Report UU-CS-2004-050, Institute for Information and Computing Sciences, Utrecht University, Utrecht, The Netherlands (2004)"},{"key":"11_CR17","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":"11_CR18","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":"11_CR19","unstructured":"Ramachandramurthi, S.: Algorithms for VLSI Layout Based on Graph Width Metrics. PhD thesis, Computer Science Department, University of Tennessee, Knoxville, Tennessee, USA (1994)"},{"key":"11_CR20","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":"11_CR21","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N. Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms\u00a07, 309\u2013322 (1986)","journal-title":"J. Algorithms"},{"issue":"2","key":"11_CR22","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/BF01215352","volume":"14","author":"P.D. Seymour","year":"1994","unstructured":"Seymour, P.D., Thomas, R.: Call routing and the ratcatcher. Combinatorica\u00a014(2), 217\u2013241 (1994)","journal-title":"Combinatorica"},{"key":"11_CR23","unstructured":"Treewidthlib. 2004-03-31, \n                    \n                      http:\/\/www.cs.uu.nl\/people\/hansb\/treewidthlib"},{"key":"11_CR24","unstructured":"Wolle, T., Koster, A.M.C.A., Bodlaender, H.L.: A note on contraction degeneracy. Technical Report UU-CS-2004-042, Institute of Information and Computing Sciences, Utrecht University, Utrecht, The Netherlands (2004)"}],"container-title":["Lecture Notes in Computer Science","Experimental and Efficient Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11427186_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T20:00:27Z","timestamp":1558296027000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11427186_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540259206","9783540320784"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/11427186_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}