{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T14:13:29Z","timestamp":1781014409378,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642280498","type":"print"},{"value":"9783642280504","type":"electronic"}],"license":[{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"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":[[2012]]},"DOI":"10.1007\/978-3-642-28050-4_18","type":"book-chapter","created":{"date-parts":[[2012,3,8]],"date-time":"2012-03-08T23:40:26Z","timestamp":1331250026000},"page":"219-231","source":"Crossref","is-referenced-by-count":5,"title":["Finding Good Decompositions for Dynamic Programming on Dense Graphs"],"prefix":"10.1007","author":[{"given":"Eivind Magnus","family":"Hvidevold","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sadia","family":"Sharmin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jan Arne","family":"Telle","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Martin","family":"Vatshelle","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"18_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/978-3-642-16926-7_16","volume-title":"Graph Theoretic Concepts in Computer Science","author":"I. Adler","year":"2010","unstructured":"Adler, I., Bui-Xuan, B.M., Rabinovich, Y., Renault, G., Telle, J.A., Vatshelle, M.: On the Boolean-Width of a Graph: Structure and Applications. In: Thilikos, D.M. (ed.) WG 2010. LNCS, vol.\u00a06410, pp. 159\u2013170. Springer, Heidelberg (2010)"},{"key":"18_CR2","doi-asserted-by":"crossref","unstructured":"Belmonte, R., Vatshelle, M.: Graph classes with structured neighborhoods and algorithmic applications. In: Proceedings of the 37th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2011 (2011), \n                  \n                    www.ii.uib.no\/~martinv\/Papers\/LogBoolw.pdf","DOI":"10.1007\/978-3-642-25870-1_6"},{"key":"18_CR3","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 Journal on Computing\u00a025, 1305\u20131317 (1996)","journal-title":"SIAM Journal on Computing"},{"key":"18_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/11917496_1","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"H.L. Bodlaender","year":"2006","unstructured":"Bodlaender, H.L.: Treewidth: Characterizations, Applications, and Computations. In: Fomin, F.V. (ed.) WG 2006. LNCS, vol.\u00a04271, pp. 1\u201314. Springer, Heidelberg (2006)"},{"key":"18_CR5","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1016\/j.ic.2009.03.008","volume":"208","author":"H.L. Bodlaender","year":"2010","unstructured":"Bodlaender, H.L., Koster, A.M.C.A.: Treewidth computations I. Upper bounds. Information and Computation\u00a0208, 259\u2013275 (2010)","journal-title":"Information and Computation"},{"key":"18_CR6","unstructured":"Bodlaender, H.L., Koster, A.M.C.A.: Treewidth computations II. lower bounds. Technical Report UU-CS-2010-022, Department of Information and Computing Sciences, Utrecht University, Utrecht, The Netherlands (2010) (accepted for publication in Information and Computation)"},{"key":"18_CR7","unstructured":"Brandstadt, A.: Personal Communication"},{"key":"18_CR8","doi-asserted-by":"crossref","unstructured":"Bui-Xuan, B.M., Telle, J.A., Vatshelle, M.: Boolean-width of graphs. Theoretical Computer Science (to appear, 2011), \n                  \n                    www.ii.uib.no\/~telle\/bib\/listofpub\/BTV11.pdf","DOI":"10.1016\/j.tcs.2011.05.022"},{"key":"18_CR9","unstructured":"Chen, H.: Quantified constraint satisfaction and bounded treewidth. In: de M\u00e1ntaras, R.L., Saitta, L. (eds.) Proceedings of the 17th European Conference on Artificial Intelligence, ECAI 2004, pp. 161\u2013165 (2004)"},{"key":"18_CR10","unstructured":"The second DIMACS implementation challenge: NP-Hard Problems: Maximum Clique, Graph Coloring, and Satisfiability (1992-1993), \n                  \n                    http:\/\/dimacs.rutgers.edu\/Challenges\/"},{"key":"18_CR11","first-page":"243","volume":"124","author":"G. Gottlob","year":"2000","unstructured":"Gottlob, G., Leone, N., Scarcello, F.: A comparison of structural CSP decomposition methods. Acta Informatica\u00a0124, 243\u2013282 (2000)","journal-title":"Acta Informatica"},{"key":"18_CR12","doi-asserted-by":"crossref","unstructured":"Hicks, I.V., Koster, A.M.C.A., Koloto\u011flu, E.: Branch and tree decomposition techniques for discrete optimization. In: Cole Smith, J. (ed.) INFORMS Annual Meeting, TutORials 2005. INFORMS Tutorials in Operations Research Series, ch. 1, pp. 1\u201329 (2005)","DOI":"10.1287\/educ.1053.0017"},{"key":"18_CR13","doi-asserted-by":"publisher","first-page":"1012","DOI":"10.1137\/070685920","volume":"38","author":"P. Hlin\u011bn\u00fd","year":"2008","unstructured":"Hlin\u011bn\u00fd, P., Oum, S.: Finding branch-decomposition and rank-decomposition. SIAM Journal on Computing\u00a038, 1012\u20131032 (2008)","journal-title":"SIAM Journal on Computing"},{"key":"18_CR14","unstructured":"Kim, K.H.: Boolean matrix theory and its applications. Marcel Dekker (1982)"},{"key":"18_CR15","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":"18_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"444","DOI":"10.1007\/978-3-642-18381-2_37","volume-title":"SOFSEM 2011: Theory and Practice of Computer Science","author":"A. Overwijk","year":"2011","unstructured":"Overwijk, A., Penninkx, E., Bodlaender, H.L.: A Local Search Algorithm for Branchwidth. In: \u010cern\u00e1, I., Gyim\u00f3thy, T., Hromkovi\u010d, J., Jefferey, K., Kr\u00e1lovi\u0107, R., Vukoli\u0107, M., Wolf, S. (eds.) SOFSEM 2011. LNCS, vol.\u00a06543, pp. 444\u2013454. Springer, Heidelberg (2011)"},{"key":"18_CR17","unstructured":"R\u00f6hrig, H.: Tree decomposition: A feasibility study. Master\u2019s thesis, Max-Planck-Institut f\u00fcr Informatik, Saarbr\u00fccken, Germany (1998)"},{"key":"18_CR18","doi-asserted-by":"crossref","unstructured":"Song, Y., Liu, C., Malmberg, R., Pan, F., Cai, L.: Tree decomposition based fast search of RNA structures including pseudoknots in genomes. In: Proceedings of the 2005 IEEE Computational Systems Bioinformatics Conference, CSB 2005, pp. 223\u2013234 (2005)","DOI":"10.1109\/CSB.2005.52"},{"key":"18_CR19","unstructured":"Treewidthlib (2004), \n                  \n                    http:\/\/www.cs.uu.nl\/people\/hansb\/treewidthlib"},{"key":"18_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1007\/978-3-642-04128-0_51","volume-title":"Algorithms - ESA 2009","author":"J.M.M. Rooij van","year":"2009","unstructured":"van Rooij, J.M.M., Bodlaender, H.L., Rossmanith, P.: Dynamic Programming on Tree Decompositions using Generalised Fast Subset Convolution. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol.\u00a05757, pp. 566\u2013577. Springer, Heidelberg (2009)"},{"key":"18_CR21","doi-asserted-by":"crossref","unstructured":"Zhao, J., Che, D., Cai, L.: Comparative pathway annotation with protein-DNA interaction and operon information via graph tree decomposition. In: Proceedings of Pacific Symposium on Biocomputing, PSB 2007, vol.\u00a012, pp. 496\u2013507 (2007)","DOI":"10.1142\/9789812772435_0047"},{"issue":"1-2","key":"18_CR22","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/s00285-007-0124-4","volume":"56","author":"J. Zhao","year":"2008","unstructured":"Zhao, J., Malmberg, R.L., Cai, L.: Rapid ab initio prediction of RNA pseudoknots via graph tree decomposition. Journal of Mathematical Biology\u00a056(1-2), 145\u2013159 (2008)","journal-title":"Journal of Mathematical Biology"}],"container-title":["Lecture Notes in Computer Science","Parameterized and Exact Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-28050-4_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,28]],"date-time":"2019-04-28T09:34:13Z","timestamp":1556444053000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-28050-4_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642280498","9783642280504"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-28050-4_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012]]}}}