{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T18:22:24Z","timestamp":1743013344553,"version":"3.40.3"},"publisher-location":"Cham","reference-count":42,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030247652"},{"type":"electronic","value":"9783030247669"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-030-24766-9_4","type":"book-chapter","created":{"date-parts":[[2019,7,30]],"date-time":"2019-07-30T23:09:48Z","timestamp":1564528188000},"page":"43-56","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Positive-Instance Driven Dynamic Programming for Graph Searching"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6475-5512","authenticated-orcid":false,"given":"Max","family":"Bannach","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4177-8081","authenticated-orcid":false,"given":"Sebastian","family":"Berndt","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,7,12]]},"reference":[{"issue":"2","key":"4_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. Algebraic Discrete Methods 8(2), 277\u2013284 (1987)","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"4_CR2","unstructured":"Bannach, M., Berndt, S., , T.E.: Jdrasil (2017). https:\/\/github.com\/maxbannach\/Jdrasil. Accessed 09 Feb 2019"},{"key":"4_CR3","unstructured":"Bannach, M., Berndt, S.: Practical access to dynamic programming on tree decompositions. In: ESA, pp. 6:1\u20136:13 (2018)"},{"key":"4_CR4","unstructured":"Bannach, M., Berndt, S., Ehlers, T.: Jdrasil: a modular library for computing tree decompositions. In: SEA, pp. 28:1\u201328:21 (2017)"},{"key":"4_CR5","unstructured":"Berg, J., J\u00e4rvisalo, M., Malone, B.: Learning optimal bounded treewidth bayesian networks via maximum satisfiability. In: Artificial Intelligence and Statistics, pp. 86\u201395 (2014)"},{"issue":"2","key":"4_CR6","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/0196-6774(91)90003-H","volume":"12","author":"D Bienstock","year":"1991","unstructured":"Bienstock, D., Seymour, P.D.: Monotonicity in graph searching. J. Algorithms 12(2), 239\u2013245 (1991)","journal-title":"J. Algorithms"},{"key":"4_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/978-3-540-24605-3_24","volume-title":"Theory and Applications of Satisfiability Testing","author":"P Bjesse","year":"2004","unstructured":"Bjesse, P., Kukula, J., Damiano, R., Stanion, T., Zhu, Y.: Guiding SAT diagnosis with tree decompositions. In: Giunchiglia, E., Tacchella, A. (eds.) SAT 2003. LNCS, vol. 2919, pp. 315\u2013329. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-24605-3_24"},{"issue":"6","key":"4_CR8","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25(6), 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"key":"4_CR9","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/j.dam.2015.01.015","volume":"216","author":"HL Bodlaender","year":"2017","unstructured":"Bodlaender, H.L., Kratsch, S., Kreuzen, V.J.C., Kwon, O., Ok, S.: Characterizing width two for variants of treewidth. Discrete Appl. Math. 216, 29\u201346 (2017)","journal-title":"Discrete Appl. Math."},{"key":"4_CR10","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/978-1-4612-0619-4_7","volume-title":"Modern Graph Theory","author":"B Bollob\u00e1s","year":"1998","unstructured":"Bollob\u00e1s, B.: Random graphs. In: Bollob\u00e1s, B. (ed.) Modern Graph Theory, pp. 215\u2013252. Springer, New York (1998). https:\/\/doi.org\/10.1007\/978-1-4612-0619-4_7"},{"issue":"1\u20132","key":"4_CR11","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/S0304-3975(01)00007-X","volume":"276","author":"V Bouchitt\u00e9","year":"2002","unstructured":"Bouchitt\u00e9, V., Todinca, I.: Listing all potential maximal cliques of a graph. Theor. Comput. Sci. 276(1\u20132), 17\u201332 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"4_CR12","unstructured":"Charwat, G., Woltran, S.: Dynamic programming-based QBF solving. In: QBF, pp. 27\u201340 (2016)"},{"issue":"6","key":"4_CR13","doi-asserted-by":"publisher","first-page":"866","DOI":"10.1016\/j.dam.2010.12.017","volume":"160","author":"B Courcelle","year":"2012","unstructured":"Courcelle, B.: On the model-checking of monadic second-order formulas with edge set quantifications. Discrete Appl. Math. 160(6), 866\u2013887 (2012)","journal-title":"Discrete Appl. Math."},{"key":"4_CR14","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., et al.: Parameterized Algorithms. Springer, Berlin Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3"},{"issue":"3","key":"4_CR15","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1145\/765568.765570","volume":"50","author":"A Darwiche","year":"2003","unstructured":"Darwiche, A.: A differential approach to inference in bayesian networks. J. ACM (JACM) 50(3), 280\u2013305 (2003)","journal-title":"J. ACM (JACM)"},{"key":"4_CR16","unstructured":"Dell, H., Husfeldt, T., Jansen, B., Kaski, P., Komusiewicz, C., Rosamond, F.: The first parameterized algorithms and computational experiments challenge. In: IPEC 2016, pp. 30:1\u201330:9 (2017)"},{"key":"4_CR17","unstructured":"Dell, H., Komusiewicz, C., Talmon, N., Weller, M.: The PACE 2017 parameterized algorithms and computational experiments challenge: the second iteration. In: IPEC 2017 (2018)"},{"key":"4_CR18","unstructured":"Eiben, E., Ganian, R., Ordyniak, S.: Small resolution proofs for QBF using dependency treewidth. In: STACS. LIPIcs, vol. 96, pp. 28:1\u201328:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2018)"},{"key":"4_CR19","unstructured":"Eisenbrand, F., Hunkenschr\u00f6der, C., Klein, K.: Faster algorithms for integer programs with block structure. In: ICALP. LIPIcs, vol. 107, pp. 49:1\u201349:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2018)"},{"issue":"Dec","key":"4_CR20","first-page":"2699","volume":"9","author":"G Elidan","year":"2008","unstructured":"Elidan, G., Gould, S.: Learning bounded treewidth bayesian networks. J. Mach. Learn. Res. 9(Dec), 2699\u20132731 (2008)","journal-title":"J. Mach. Learn. Res."},{"key":"4_CR21","unstructured":"Fichte, J.K., Hecher, M., Woltran, S., Zisser, M.: Weighted model counting on the GPU by exploiting small treewidth. In: ESA, pp. 28:1\u201328:16 (2018)"},{"issue":"3","key":"4_CR22","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1007\/s00453-007-9041-6","volume":"53","author":"F Fomin","year":"2009","unstructured":"Fomin, F., Fraigniaud, P., Nisse, N.: Nondeterministic graph searching: from pathwidth to treewidth. Algorithmica 53(3), 358\u2013373 (2009)","journal-title":"Algorithmica"},{"key":"4_CR23","series-title":"Texts in Theoretical Computer Science. An EATCS Series","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16533-7","volume-title":"Exact Exponential Algorithms","author":"FV Fomin","year":"2010","unstructured":"Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. Texts in Theoretical Computer Science. An EATCS Series. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-16533-7"},{"key":"4_CR24","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/j.artint.2017.12.006","volume":"257","author":"R Ganian","year":"2018","unstructured":"Ganian, R., Ordyniak, S.: The complexity landscape of decompositional parameters for ILP. Artif. Intell. 257, 61\u201371 (2018)","journal-title":"Artif. Intell."},{"key":"4_CR25","doi-asserted-by":"crossref","unstructured":"Ganian, R., Ordyniak, S., Ramanujan, M.S.: Going beyond primal treewidth for (M)ILP. In: AAAI, pp. 815\u2013821. AAAI Press (2017)","DOI":"10.1609\/aaai.v31i1.10644"},{"issue":"15","key":"4_CR26","doi-asserted-by":"publisher","first-page":"2089","DOI":"10.1016\/j.dam.2012.03.015","volume":"160","author":"A Giannopoulou","year":"2012","unstructured":"Giannopoulou, A., Hunter, P., Thilikos, D.: LIFO-search: a min-max theorem and a searching game for cycle-rank and tree-depth. Discrete Appl. Math. 160(15), 2089\u20132097 (2012)","journal-title":"Discrete Appl. Math."},{"key":"4_CR27","doi-asserted-by":"crossref","unstructured":"Habet, D., Paris, L., Terrioux, C.: A tree decomposition based approach to solve structured SAT instances. In: ICTAI, pp. 115\u2013122 (2009)","DOI":"10.1109\/ICTAI.2009.76"},{"key":"4_CR28","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0539-5","volume-title":"Descriptive Complexity","author":"N Immerman","year":"1999","unstructured":"Immerman, N.: Descriptive Complexity. Springer, Heidelberg (1999). https:\/\/doi.org\/10.1007\/978-1-4612-0539-5"},{"key":"4_CR29","doi-asserted-by":"crossref","unstructured":"Johnson, D.S., Trick, M.A.: Cliques, coloring, and satisfiability: second DIMACS implementation challenge, 11\u201313 October 1993, vol. 26. American Mathematical Soc. (1996)","DOI":"10.1090\/dimacs\/026"},{"issue":"11","key":"4_CR30","doi-asserted-by":"publisher","first-page":"558","DOI":"10.1145\/368996.369025","volume":"5","author":"AB Kahn","year":"1962","unstructured":"Kahn, A.B.: Topological sorting of large networks. Commun. ACM 5(11), 558\u2013562 (1962)","journal-title":"Commun. ACM"},{"key":"4_CR31","doi-asserted-by":"crossref","unstructured":"Karakashian, S., Woodward, R.J., Choueiry, B.Y.: Improving the performance of consistency algorithms by localizing and bolstering propagation in a tree decomposition. In: AAAI (2013)","DOI":"10.1609\/aaai.v27i1.8594"},{"issue":"4","key":"4_CR32","doi-asserted-by":"publisher","first-page":"568","DOI":"10.1016\/j.disopt.2011.06.001","volume":"8","author":"J Kneis","year":"2011","unstructured":"Kneis, J., Langer, A., Rossmanith, P.: Courcelle\u2019s theorem - a game-theoretic approach. Discrete Optim. 8(4), 568\u2013594 (2011)","journal-title":"Discrete Optim."},{"issue":"3","key":"4_CR33","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1002\/net.10046","volume":"40","author":"AMCA 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 40(3), 170\u2013180 (2002)","journal-title":"Networks"},{"key":"4_CR34","unstructured":"Kouteck\u00fd, M., Levin, A., Onn, S.: A parameterized strongly polynomial algorithm for block structured integer programs. In: ICALP. LIPIcs, vol. 107, pp. 85:1\u201385:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2018)"},{"key":"4_CR35","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1145\/151261.151263","volume":"40","author":"A LaPaugh","year":"1993","unstructured":"LaPaugh, A.: Recontamination does not help to search a graph. J. ACM 40, 224\u2013245 (1993)","journal-title":"J. ACM"},{"key":"4_CR36","unstructured":"Larisch, L., Salfelder, F.: p17 (2017). https:\/\/github.com\/freetdi\/p17. Accessed 02 Aug 2017"},{"issue":"3","key":"4_CR37","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/j.tcs.2008.02.036","volume":"399","author":"F Mazoit","year":"2008","unstructured":"Mazoit, F., Nisse, N.: Monotonicity of non-deterministic graph searching. TCS 399(3), 169\u2013178 (2008)","journal-title":"TCS"},{"key":"4_CR38","unstructured":"R\u00f6hrig, H.: Tree decomposition: a feasibility Study. Diploma thesis, Max-Planck-Institut f\u00fcr Informatik in Saarbr\u00fccken (1998)"},{"key":"4_CR39","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1006\/jctb.1993.1027","volume":"58","author":"P Seymour","year":"1993","unstructured":"Seymour, P., Thomas, R.: Graph searching and a min-max theorem for tree-width. JCT 58, 22\u201333 (1993)","journal-title":"JCT"},{"key":"4_CR40","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1007\/978-3-540-24605-3_15","volume-title":"Theory and Applications of Satisfiability Testing","author":"S Szeider","year":"2004","unstructured":"Szeider, S.: On fixed-parameter tractable parameterizations of SAT. In: Giunchiglia, E., Tacchella, A. (eds.) SAT 2003. LNCS, vol. 2919, pp. 188\u2013202. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-24605-3_15"},{"key":"4_CR41","unstructured":"Tamaki, H.: treewidth-exact (2016). https:\/\/github.com\/TCS-Meiji\/treewidth-exact. Accessed 02 Aug 2017"},{"key":"4_CR42","unstructured":"Tamaki, H.: Positive-instance driven dynamic programming for treewidth. In: ESA, pp. 68:1\u201368:13 (2017)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-24766-9_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T17:52:25Z","timestamp":1710265945000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-24766-9_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030247652","9783030247669"],"references-count":42,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-24766-9_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"12 July 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WADS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Workshop on Algorithms and Data Structures","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Edmonton, AB","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Canada","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 August 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"7 August 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wads2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.wads.org\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}