{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,8]],"date-time":"2025-05-08T11:24:54Z","timestamp":1746703494081,"version":"3.40.3"},"publisher-location":"Cham","reference-count":77,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030420703"},{"type":"electronic","value":"9783030420710"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-030-42071-0_10","type":"book-chapter","created":{"date-parts":[[2020,4,22]],"date-time":"2020-04-22T17:02:44Z","timestamp":1587574964000},"page":"129-144","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Four Shorts Stories on Surprising Algorithmic Uses of Treewidth"],"prefix":"10.1007","author":[{"given":"D\u00e1niel","family":"Marx","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,4,20]]},"reference":[{"issue":"4","key":"10_CR1","doi-asserted-by":"publisher","first-page":"814","DOI":"10.1002\/jgt.22109","volume":"85","author":"P Aboulker","year":"2017","unstructured":"Aboulker, P., Brettell, N., Havet, F., Marx, D., Trotignon, N.: Coloring graphs with constraints on connectivity. J. Graph Theory 85(4), 814\u2013838 (2017)","journal-title":"J. Graph Theory"},{"issue":"2","key":"10_CR2","doi-asserted-by":"publisher","first-page":"629","DOI":"10.1137\/S0895480104444776","volume":"22","author":"S Ahal","year":"2008","unstructured":"Ahal, S., Rabinovich, Y.: On complexity of the subpattern problem. SIAM J. Discret. Math. 22(2), 629\u2013649 (2008). https:\/\/doi.org\/10.1137\/S0895480104444776","journal-title":"SIAM J. Discret. Math."},{"key":"10_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1007\/3-540-45678-3_31","volume-title":"Algorithms and Computation","author":"MH Albert","year":"2001","unstructured":"Albert, M.H., Aldred, R.E.L., Atkinson, M.D., Holton, D.A.: Algorithms for pattern involvement in permutations. In: Eades, P., Takaoka, T. (eds.) ISAAC 2001. LNCS, vol. 2223, pp. 355\u2013367. Springer, Heidelberg (2001). https:\/\/doi.org\/10.1007\/3-540-45678-3_31. http:\/\/dl.acm.org\/citation.cfm?id=646344.689586"},{"issue":"4","key":"10_CR4","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM 42(4), 844\u2013856 (1995). https:\/\/doi.org\/10.1145\/210332.210337","journal-title":"J. ACM"},{"key":"10_CR5","unstructured":"Beigel, R.: Finding maximum independent sets in sparse and general graphs. In: Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, Baltimore, Maryland, USA, 17\u201319 January 1999, pp. 856\u2013857 (1999). http:\/\/dl.acm.org\/citation.cfm?id=314500.314969"},{"key":"10_CR6","unstructured":"Berendsohn, B.A., Kozma, L., Marx, D.: Finding and counting permutations via CSPs, accepted to IPEC (2019)"},{"issue":"2","key":"10_CR7","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1016\/0097-3165(73)90016-2","volume":"14","author":"U Bertel\u00e8","year":"1973","unstructured":"Bertel\u00e8, U., Brioschi, F.: On non-serial dynamic programming. J. Comb. Theory Ser. A 14(2), 137\u2013148 (1973). https:\/\/doi.org\/10.1016\/0097-3165(73)90016-2","journal-title":"J. Comb. Theory Ser. A"},{"key":"10_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"578","DOI":"10.1007\/978-3-642-04128-0_52","volume-title":"Algorithms - ESA 2009","author":"A Bj\u00f6rklund","year":"2009","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Counting paths and packings in halves. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol. 5757, pp. 578\u2013586. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-04128-0_52"},{"key":"10_CR9","doi-asserted-by":"publisher","unstructured":"Bj\u00f6rklund, A., Kaski, P., Kowalik, L.: Counting thin subgraphs via packings faster than meet-in-the-middle time. In: Proceedings of the 25th Annual Symposium on Discrete Algorithms (SODA), pp. 594\u2013603 (2014). https:\/\/doi.org\/10.1137\/1.9781611973402.45","DOI":"10.1137\/1.9781611973402.45"},{"issue":"2","key":"10_CR10","doi-asserted-by":"publisher","first-page":"569","DOI":"10.1007\/s00453-015-0054-2","volume":"76","author":"I Bliznets","year":"2016","unstructured":"Bliznets, I., Fomin, F.V., Pilipczuk, M., Villanger, Y.: Largest chordal andinterval subgraphs faster than $$2^n$$. Algorithmica 76(2), 569\u2013594 (2016). https:\/\/doi.org\/10.1007\/s00453-015-0054-2","journal-title":"Algorithmica"},{"key":"10_CR11","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/j.ic.2014.12.008","volume":"243","author":"HL Bodlaender","year":"2015","unstructured":"Bodlaender, H.L., Cygan, M., Kratsch, S., Nederlof, J.: Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Inf. Comput. 243, 86\u2013111 (2015). https:\/\/doi.org\/10.1016\/j.ic.2014.12.008","journal-title":"Inf. Comput."},{"issue":"2","key":"10_CR12","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1137\/130947374","volume":"45","author":"HL Bodlaender","year":"2016","unstructured":"Bodlaender, H.L., Drange, P.G., Dregi, M.S., Fomin, F.V., Lokshtanov, D., Pilipczuk, M.: A $$c^k\\cdot n$$ 5-approximation algorithm for treewidth. SIAMJ. Comput. 45(2), 317\u2013378 (2016). https:\/\/doi.org\/10.1137\/130947374","journal-title":"SIAMJ. Comput."},{"key":"10_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1007\/978-3-642-11269-0_4","volume-title":"Parameterized and Exact Computation","author":"HL Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Lokshtanov, D., Penninkx, E.: Planar capacitated dominating set is W[1]-Hard. In: Chen, J., Fomin, F.V. (eds.) IWPEC 2009. LNCS, vol. 5917, pp. 50\u201360. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-11269-0_4"},{"issue":"2","key":"10_CR14","doi-asserted-by":"publisher","first-page":"149","DOI":"10.14778\/3149193.3149196","volume":"11","author":"A Bonifati","year":"2017","unstructured":"Bonifati, A., Martens, W., Timm, T.: An analytical study of large SPARQL query logs. PVLDB 11(2), 149\u2013161 (2017). https:\/\/doi.org\/10.14778\/3149193.3149196. http:\/\/www.vldb.org\/pvldb\/vol11\/p149-bonifati.pdf","journal-title":"PVLDB"},{"key":"10_CR15","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/3-540-33700-8_18","volume":"26","author":"C Borgs","year":"2006","unstructured":"Borgs, C., Chayes, J., Lov\u00e1sz, L., S\u00f3s, V.T., Vesztergombi, K.: Counting graph homomorphisms. Top. Discret. Math. 26, 315\u2013371 (2006). https:\/\/doi.org\/10.1007\/3-540-33700-8_18","journal-title":"Top. Discret. Math."},{"issue":"5","key":"10_CR16","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/S0020-0190(97)00209-3","volume":"65","author":"P Bose","year":"1998","unstructured":"Bose, P., Buss, J.F., Lubiw, A.: Pattern matching for permutations. Inf. Process. Lett. 65(5), 277\u2013283 (1998). https:\/\/doi.org\/10.1016\/S0020-0190(97)00209-3","journal-title":"Inf. Process. Lett."},{"key":"10_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/978-3-540-79723-4_7","volume-title":"Parameterized and Exact Computation","author":"N Bourgeois","year":"2008","unstructured":"Bourgeois, N., Escoffier, B., Paschos, V.T.: An\u00a0O*(1.0977n) exact algorithm for max independent set in sparse graphs. In: Grohe, M., Niedermeier, R. (eds.) IWPEC 2008. LNCS, vol. 5018, pp. 55\u201365. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-79723-4_7"},{"issue":"1\u20132","key":"10_CR18","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1007\/s00453-010-9460-7","volume":"62","author":"N Bourgeois","year":"2012","unstructured":"Bourgeois, N., Escoffier, B., Paschos, V.T., van Rooij, J.M.M.: Fast algorithmsfor max independent set. Algorithmica 62(1\u20132), 382\u2013415 (2012). https:\/\/doi.org\/10.1007\/s00453-010-9460-7","journal-title":"Algorithmica"},{"issue":"3","key":"10_CR19","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1007\/s00224-007-1346-y","volume":"41","author":"L Cai","year":"2007","unstructured":"Cai, L., Fellows, M.R., Juedes, D.W., Rosamond, F.A.: The complexity of polynomial-time approximation. Theory Comput. Syst. 41(3), 459\u2013477 (2007). https:\/\/doi.org\/10.1007\/s00224-007-1346-y","journal-title":"Theory Comput. Syst."},{"issue":"4","key":"10_CR20","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/s00453-004-1145-7","volume":"43","author":"J Chen","year":"2005","unstructured":"Chen, J., Kanj, I.A., Xia, G.: Labeled search trees and amortized analysis: Improved upper bounds for np-hard problems. Algorithmica 43(4), 245\u2013273 (2005). https:\/\/doi.org\/10.1007\/s00453-004-1145-7","journal-title":"Algorithmica"},{"key":"10_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"352","DOI":"10.1007\/978-3-642-39206-1_30","volume-title":"Automata, Languages, and Programming","author":"R Curticapean","year":"2013","unstructured":"Curticapean, R.: Counting matchings of size k Is $$\\sharp $$W[1]-Hard. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013. LNCS, vol. 7965, pp. 352\u2013363. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-39206-1_30"},{"key":"10_CR22","doi-asserted-by":"publisher","unstructured":"Curticapean, R., Dell, H., Marx, D.: Homomorphisms are a good basis for counting small subgraphs. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, 19\u201323 June 2017, pp. 210\u2013223 (2017). https:\/\/doi.org\/10.1145\/3055399.3055502","DOI":"10.1145\/3055399.3055502"},{"key":"10_CR23","doi-asserted-by":"publisher","unstructured":"Curticapean, R., Marx, D.: Complexity of counting subgraphs: only the boundedness of the vertex-cover number counts. In: 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, 18\u201321 October 2014, pp. 130\u2013139 (2014). https:\/\/doi.org\/10.1109\/FOCS.2014.22","DOI":"10.1109\/FOCS.2014.22"},{"key":"10_CR24","doi-asserted-by":"publisher","unstructured":"Cygan, M., Kowalik, L., Socala, A.: Improving TSP tours using dynamic programming over tree decompositions. In: 25th Annual European Symposium on Algorithms, ESA 2017, 4\u20136 September 2017, Vienna, Austria, pp. 30:1\u201330:14 (2017). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2017.30","DOI":"10.4230\/LIPIcs.ESA.2017.30"},{"key":"10_CR25","doi-asserted-by":"publisher","unstructured":"Cygan, M., Nederlof, J., Pilipczuk, M., Pilipczuk, M., van Rooij, J.M.M., Wojtaszczyk, J.O.: Solving connectivity problems parameterized by treewidth in single exponential time. In: Ostrovsky, R. (ed.) IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, 22\u201325 October 2011, pp. 150\u2013159. IEEE Computer Society (2011). https:\/\/doi.org\/10.1109\/FOCS.2011.23","DOI":"10.1109\/FOCS.2011.23"},{"issue":"2","key":"10_CR26","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/s00453-013-9796-x","volume":"70","author":"M Cygan","year":"2014","unstructured":"Cygan, M., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: Solving the 2-disjoint connected subgraphs problem faster than 2 n. Algorithmica 70(2), 195\u2013207 (2014). https:\/\/doi.org\/10.1007\/s00453-013-9796-x","journal-title":"Algorithmica"},{"issue":"3","key":"10_CR27","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1016\/0004-3702(89)90037-4","volume":"38","author":"R Dechter","year":"1989","unstructured":"Dechter, R., Pearl, J.: Tree clustering for constraint networks. Artif. Intell. 38(3), 353\u2013366 (1989). https:\/\/doi.org\/10.1016\/0004-3702(89)90037-4. http:\/\/www.sciencedirect.com\/science\/article\/pii\/0004370289900374","journal-title":"Artif. Intell."},{"issue":"3","key":"10_CR28","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1137\/S0895480103433410","volume":"18","author":"ED Demaine","year":"2004","unstructured":"Demaine, E.D., Fomin, F.V., Hajiaghayi, M.T., Thilikos, D.M.: Bidimensional parameters and local treewidth. SIAM J. Discret. Math. 18(3), 501\u2013511 (2004). https:\/\/doi.org\/10.1137\/S0895480103433410","journal-title":"SIAM J. Discret. Math."},{"issue":"1","key":"10_CR29","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1145\/1077464.1077468","volume":"1","author":"ED Demaine","year":"2005","unstructured":"Demaine, E.D., Fomin, F.V., Hajiaghayi, M.T., Thilikos, D.M.: Fixed-parameteralgorithms for ($$k$$, $$r$$)-center in planar graphs and map graphs. ACM Trans. Algorithms 1(1), 33\u201347 (2005). https:\/\/doi.org\/10.1145\/1077464.1077468","journal-title":"ACM Trans. Algorithms"},{"issue":"6","key":"10_CR30","doi-asserted-by":"publisher","first-page":"866","DOI":"10.1145\/1101821.1101823","volume":"52","author":"ED Demaine","year":"2005","unstructured":"Demaine, E.D., Fomin, F.V., Hajiaghayi, M.T., Thilikos, D.M.: Subexponential parameterized algorithms on bounded-genus graphs and $$H$$-minor-freegraphs. J. ACM 52(6), 866\u2013893 (2005). https:\/\/doi.org\/10.1145\/1101821.1101823","journal-title":"J. ACM"},{"issue":"4","key":"10_CR31","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/s00453-004-1125-y","volume":"41","author":"ED Demaine","year":"2005","unstructured":"Demaine, E.D., Hajiaghayi, M.T., Thilikos, D.M.: Exponential speedup offixed-parameter algorithms for classes of graphs excluding single-crossinggraphs as minors. Algorithmica 41(4), 245\u2013267 (2005). https:\/\/doi.org\/10.1007\/s00453-004-1125-y","journal-title":"Algorithmica"},{"issue":"1\u20132","key":"10_CR32","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/S0304-3975(02)00017-8","volume":"281","author":"J D\u00edaz","year":"2002","unstructured":"D\u00edaz, J., Serna, M.J., Thilikos, D.M.: Counting H-colorings of partial k-trees. Theor. Comput. Sci. 281(1\u20132), 291\u2013309 (2002). https:\/\/doi.org\/10.1016\/S0304-3975(02)00017-8","journal-title":"Theor. Comput. Sci."},{"issue":"7","key":"10_CR33","doi-asserted-by":"publisher","first-page":"800","DOI":"10.1016\/j.dam.2009.10.011","volume":"158","author":"F Dorn","year":"2010","unstructured":"Dorn, F.: Dynamic programming and planarity: Improved tree-decomposition basedalgorithms. Discret. Appl. Math. 158(7), 800\u2013808 (2010). https:\/\/doi.org\/10.1016\/j.dam.2009.10.011","journal-title":"Discret. Appl. Math."},{"key":"10_CR34","doi-asserted-by":"publisher","unstructured":"Dorn, F.: Planar subgraph isomorphism revisited. In: 27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010, 4\u20136 March 2010, Nancy, France, pp. 263\u2013274 (2010). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2010.2460","DOI":"10.4230\/LIPIcs.STACS.2010.2460"},{"key":"10_CR35","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1016\/j.ic.2013.11.006","volume":"233","author":"F Dorn","year":"2013","unstructured":"Dorn, F., Fomin, F.V., Lokshtanov, D., Raman, V., Saurabh, S.: Beyond bidimensionality: parameterized subexponential algorithms on directed graphs. Inf. Comput. 233, 60\u201370 (2013). https:\/\/doi.org\/10.1016\/j.ic.2013.11.006","journal-title":"Inf. Comput."},{"issue":"5","key":"10_CR36","doi-asserted-by":"publisher","first-page":"1606","DOI":"10.1016\/j.jcss.2012.02.004","volume":"78","author":"F Dorn","year":"2012","unstructured":"Dorn, F., Fomin, F.V., Thilikos, D.M.: Catalan structures and dynamic programming in h-minor-free graphs. J. Comput. Syst. Sci. 78(5), 1606\u20131622 (2012). https:\/\/doi.org\/10.1016\/j.jcss.2012.02.004","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"10_CR37","doi-asserted-by":"publisher","first-page":"790","DOI":"10.1007\/s00453-009-9296-1","volume":"58","author":"F Dorn","year":"2010","unstructured":"Dorn, F., Penninkx, E., Bodlaender, H.L., Fomin, F.V.: Efficient exact algorithms on planar graphs: exploiting sphere cut decompositions. Algorithmica 58(3), 790\u2013810 (2010). https:\/\/doi.org\/10.1007\/s00453-009-9296-1","journal-title":"Algorithmica"},{"key":"10_CR38","unstructured":"Fischl, W., Gottlob, G., Longo, D.M., Pichler, R.: Hyperbench: a benchmark and tool for hypergraphs and empirical findings. In: Proceedings of the 13th Alberto Mendelzon International Workshop on Foundations of Data Management, Asunci\u00f3n, Paraguay, 3\u20137 June 2019 (2019). http:\/\/ceur-ws.org\/Vol-2369\/short02.pdf"},{"issue":"4","key":"10_CR39","doi-asserted-by":"publisher","first-page":"892","DOI":"10.1137\/S0097539703427203","volume":"33","author":"J Flum","year":"2004","unstructured":"Flum, J., Grohe, M.: The parameterized complexity of counting problems. SIAM J. Comput. 33(4), 892\u2013922 (2004). https:\/\/doi.org\/10.1137\/S0097539703427203","journal-title":"SIAM J. Comput."},{"issue":"2","key":"10_CR40","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/s00453-007-9133-3","volume":"54","author":"FV Fomin","year":"2009","unstructured":"Fomin, F.V., Gaspers, S., Saurabh, S., Stepanov, A.A.: On two techniques ofcombining branching and treewidth. Algorithmica 54(2), 181\u2013207 (2009). https:\/\/doi.org\/10.1007\/s00453-007-9133-3","journal-title":"Algorithmica"},{"issue":"5","key":"10_CR41","doi-asserted-by":"publisher","first-page":"25:1","DOI":"10.1145\/1552285.1552286","volume":"56","author":"FV Fomin","year":"2009","unstructured":"Fomin, F.V., Grandoni, F., Kratsch, D.: A measure & conquer approach for the analysis of exact algorithms. J. ACM 56(5), 25:1\u201325:32 (2009). https:\/\/doi.org\/10.1145\/1552285.1552286","journal-title":"J. ACM"},{"issue":"5","key":"10_CR42","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/j.ipl.2005.10.012","volume":"97","author":"FV Fomin","year":"2006","unstructured":"Fomin, F.V., H\u00f8ie, K.: Pathwidth of cubic graphs and exact algorithms. Inf. Process. Lett. 97(5), 191\u2013196 (2006). https:\/\/doi.org\/10.1016\/j.ipl.2005.10.012","journal-title":"Inf. Process. Lett."},{"key":"10_CR43","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. TTCSAES. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-16533-7"},{"key":"10_CR44","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Subexponential parameterized algorithms for planar and apex-minor-free graphs via low treewidth pattern covering. In: FOCS 2016, pp. 515\u2013524. IEEE Computer Society (2016)","DOI":"10.1109\/FOCS.2016.62"},{"issue":"4","key":"10_CR45","doi-asserted-by":"publisher","first-page":"29:1","DOI":"10.1145\/2886094","volume":"63","author":"FV Fomin","year":"2016","unstructured":"Fomin, F.V., Lokshtanov, D., Panolan, F., Saurabh, S.: Efficient computation of representative families with applications in parameterized and exact algorithms. J. ACM 63(4), 29:1\u201329:60 (2016). https:\/\/doi.org\/10.1145\/2886094","journal-title":"J. ACM"},{"issue":"2","key":"10_CR46","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1137\/S0097539702419649","volume":"36","author":"FV Fomin","year":"2006","unstructured":"Fomin, F.V., Thilikos, D.M.: Dominating sets in planar graphs: branch-width andexponential speed-up. SIAM J. Comput. 36(2), 281\u2013309 (2006). https:\/\/doi.org\/10.1137\/S0097539702419649","journal-title":"SIAM J. Comput."},{"key":"10_CR47","unstructured":"Freuder, E.C.: Complexity of k-tree structured constraint satisfaction problems. In: Proceedings of the Eighth National Conference on Artificial Intelligence, AAAI 1990, vol. 1, pp. 4\u20139. AAAI Press (1990), http:\/\/dl.acm.org\/citation.cfm?id=1865499.1865500"},{"issue":"3","key":"10_CR48","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1007\/s00453-012-9627-5","volume":"64","author":"Q Gu","year":"2012","unstructured":"Gu, Q., Tamaki, H.: Improved bounds on the planar branchwidth with respect tothe largest grid minor size. Algorithmica 64(3), 416\u2013453 (2012). https:\/\/doi.org\/10.1007\/s00453-012-9627-5","journal-title":"Algorithmica"},{"key":"10_CR49","doi-asserted-by":"publisher","unstructured":"Guillemot, S., Marx, D.: Finding small patterns in permutations in linear time. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, 5\u20137 January 2014, pp. 82\u2013101 (2014). https:\/\/doi.org\/10.1137\/1.9781611973402.7","DOI":"10.1137\/1.9781611973402.7"},{"issue":"1\u20132","key":"10_CR50","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/BF01917434","volume":"8","author":"R Halin","year":"1976","unstructured":"Halin, R.: S-functions for graphs. J. Geom. 8(1\u20132), 171\u2013186 (1976)","journal-title":"J. Geom."},{"issue":"2","key":"10_CR51","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of $$k$$-SAT. J. Comput. Syst. Sci. 62(2), 367\u2013375 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"10_CR52","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"9","key":"10_CR53","doi-asserted-by":"publisher","first-page":"847","DOI":"10.1109\/TC.1986.1676847","volume":"35","author":"T Jian","year":"1986","unstructured":"Jian, T.: $$O(2^{0.304n})$$ algorithm for solving maximum independent set problem. IEEE Trans. Comput. 35(9), 847\u2013851 (1986). https:\/\/www.scopus.com\/inward\/record.uri?eid=2-s2.0-0022787854&partnerID=40&md5=c723ea6d9074acfa3d6f6c73e3439007","journal-title":"IEEE Trans. Comput."},{"key":"10_CR54","doi-asserted-by":"crossref","unstructured":"Klein, P.N., Marx, D.: A subexponential parameterized algorithm for subset TSP on planar graphs. In: SODA 2014, pp. 1812\u20131830. SIAM (2014)","DOI":"10.1137\/1.9781611973402.131"},{"key":"10_CR55","doi-asserted-by":"publisher","unstructured":"Kneis, J., Langer, A., Rossmanith, P.: A fine-grained analysis of a simple independent set algorithm. In: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2009, 15\u201317 December 2009, IIT Kanpur, India, pp. 287\u2013298 (2009). https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2009.2326","DOI":"10.4230\/LIPIcs.FSTTCS.2009.2326"},{"key":"10_CR56","volume-title":"The Art of Computer Programming, Volume I: Fundamental Algorithms","author":"DE Knuth","year":"1968","unstructured":"Knuth, D.E.: The Art of Computer Programming, Volume I: Fundamental Algorithms. Addison-Wesley, Boston (1968)"},{"issue":"3","key":"10_CR57","doi-asserted-by":"publisher","first-page":"31:1","DOI":"10.1145\/2885499","volume":"12","author":"I Koutis","year":"2016","unstructured":"Koutis, I., Williams, R.: LIMITS and applications of group algebras for parameterized problems. ACM Trans. Algorithms 12(3), 31:1\u201331:18 (2016). https:\/\/doi.org\/10.1145\/2885499","journal-title":"ACM Trans. Algorithms"},{"key":"10_CR58","unstructured":"Lokshtanov, D., Saurabh, S., Wahlstr\u00f6m, M.: Subexponential parameterized odd cycle transversal on planar graphs. In: FSTTCS 2012. LIPIcs, vol. 18, pp. 424\u2013434. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik (2012)"},{"issue":"3\u20134","key":"10_CR59","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/BF02280291","volume":"18","author":"L Lov\u00e1sz","year":"1967","unstructured":"Lov\u00e1sz, L.: Operations with structures. Acta Math. Hungarica 18(3\u20134), 321\u2013328 (1967)","journal-title":"Acta Math. Hungarica"},{"key":"10_CR60","doi-asserted-by":"publisher","unstructured":"Maniu, S., Senellart, P., Jog, S.: An experimental study of the treewidth of real-world graph data. In: 22nd International Conference on Database Theory, ICDT 2019, 26\u201328 March 2019, Lisbon, Portugal, pp. 12:1\u201312:18 (2019). https:\/\/doi.org\/10.4230\/LIPIcs.ICDT.2019.12","DOI":"10.4230\/LIPIcs.ICDT.2019.12"},{"issue":"1","key":"10_CR61","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/j.jcta.2004.04.002","volume":"107","author":"A Marcus","year":"2004","unstructured":"Marcus, A., Tardos, G.: Excluded permutation matrices and the Stanley-Wilf conjecture. J. Comb. Theory Ser. A 107(1), 153\u2013160 (2004). https:\/\/doi.org\/10.1016\/j.jcta.2004.04.002","journal-title":"J. Comb. Theory Ser. A"},{"key":"10_CR62","doi-asserted-by":"publisher","unstructured":"Monien, B., Preis, R.: Upper bounds on the bisection width of 3- and 4-regular graphs. In: Mathematical Foundations of Computer Science 2001, 26th International Symposium, MFCS 2001 Marianske Lazne, Czech Republic, 27\u201331 August 2001, Proceedings, pp. 524\u2013536 (2001). https:\/\/doi.org\/10.1007\/3-540-44683-4_46","DOI":"10.1007\/3-540-44683-4_46"},{"key":"10_CR63","doi-asserted-by":"publisher","unstructured":"Pilipczuk, M.: Surprising applications of treewidth bounds for planar graphs. In: Fomin, F.V., et al. (eds.) Bodlaender Festschrift. LNCS, vol. 12160, pp. 173\u2013188. Springer, Heidelberg (2020). https:\/\/doi.org\/10.1007\/978-3-030-42071-0_13","DOI":"10.1007\/978-3-030-42071-0_13"},{"key":"10_CR64","unstructured":"Pilipczuk, M., Pilipczuk, M., Sankowski, P., van Leeuwen, E.J.: Subexponential-time parameterized algorithm for Steiner tree on planar graphs. In: STACS 2013. LIPIcs, vol. 20, pp. 353\u2013364. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik (2013)"},{"key":"10_CR65","doi-asserted-by":"crossref","unstructured":"Pilipczuk, M., Pilipczuk, M., Sankowski, P., van Leeuwen, E.J.: Network sparsification for steiner problems on planar and bounded-genus graphs. In: FOCS 2014, pp. 276\u2013285. IEEE Computer Society (2014)","DOI":"10.1109\/FOCS.2014.37"},{"key":"10_CR66","doi-asserted-by":"crossref","unstructured":"Razgon, I.: Computing minimum directed feedback vertex set in $${O}(1.9977^n)$$. In: Proceedings on Theoretical Computer Science, 10th Italian Conference, ICTCS 2007, Rome, Italy, 3\u20135 October 2007, pp. 70\u201381 (2007)","DOI":"10.1142\/9789812770998_0010"},{"issue":"2","key":"10_CR67","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/j.jda.2008.09.004","volume":"7","author":"I Razgon","year":"2009","unstructured":"Razgon, I.: Faster computation of maximum independent set and parameterized vertex cover for graphs with maximum degree 3. J. Discret. Algorithms 7(2), 191\u2013212 (2009). https:\/\/doi.org\/10.1016\/j.jda.2008.09.004","journal-title":"J. Discret. Algorithms"},{"issue":"2","key":"10_CR68","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., Thomas, R.: Quickly excluding a planar graph. J. Comb. Theory Ser. B 62(2), 323\u2013348 (1994). https:\/\/doi.org\/10.1006\/jctb.1994.1073","journal-title":"J. Comb. Theory Ser. B"},{"issue":"1","key":"10_CR69","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0095-8956(84)90013-3","volume":"36","author":"N Robertson","year":"1984","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. III. planar tree-width. J. Comb. Theory Ser. B 36(1), 49\u201364 (1984). https:\/\/doi.org\/10.1016\/0095-8956(84)90013-3","journal-title":"J. Comb. Theory Ser. B"},{"issue":"3","key":"10_CR70","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0196-6774(86)90032-5","volume":"7","author":"JM Robson","year":"1986","unstructured":"Robson, J.M.: Algorithms for maximum independent sets. J. Algorithms 7(3), 425\u2013440 (1986). https:\/\/doi.org\/10.1016\/0196-6774(86)90032-5","journal-title":"J. Algorithms"},{"issue":"3\u20134","key":"10_CR71","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1016\/j.disopt.2007.08.001","volume":"4","author":"AD Scott","year":"2007","unstructured":"Scott, A.D., Sorkin, G.B.: Linear-programming design and analysis of fast algorithms for Max 2-CSP. Discret. Optim. 4(3\u20134), 260\u2013287 (2007). https:\/\/doi.org\/10.1016\/j.disopt.2007.08.001","journal-title":"Discret. Optim."},{"issue":"3","key":"10_CR72","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1137\/0206038","volume":"6","author":"RE Tarjan","year":"1977","unstructured":"Tarjan, R.E., Trojanowski, A.E.: Finding a maximum independent set. SIAM J. Comput. 6(3), 537\u2013546 (1977). https:\/\/doi.org\/10.1137\/0206038","journal-title":"SIAM J. Comput."},{"issue":"2","key":"10_CR73","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1006\/inco.1997.2697","volume":"142","author":"M Thorup","year":"1998","unstructured":"Thorup, M.: All structured programs have small tree-width and good register allocation. Inf. Comput. 142(2), 159\u2013181 (1998). https:\/\/doi.org\/10.1006\/inco.1997.2697","journal-title":"Inf. Comput."},{"key":"10_CR74","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"LG Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of computing the permanent. Theor. Comput. Sci. 8, 189\u2013201 (1979). https:\/\/doi.org\/10.1016\/0304-3975(79)90044-6","journal-title":"Theor. Comput. Sci."},{"key":"10_CR75","unstructured":"West, J.: Permutations with restricted subsequences and stack-sortable permutations. Ph.D. thesis, MIT, Cambridge, MA (1990)"},{"key":"10_CR76","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/j.tcs.2012.09.022","volume":"469","author":"M Xiao","year":"2013","unstructured":"Xiao, M., Nagamochi, H.: Confining sets and avoiding bottleneck cases: a simple maximum independent set algorithm in degree-3 graphs. Theor. Comput. Sci. 469, 92\u2013104 (2013). https:\/\/doi.org\/10.1016\/j.tcs.2012.09.022","journal-title":"Theor. Comput. Sci."},{"key":"10_CR77","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1016\/j.ic.2017.06.001","volume":"255","author":"M Xiao","year":"2017","unstructured":"Xiao, M., Nagamochi, H.: Exact algorithms for maximum independent set. Inf. Comput. 255, 126\u2013146 (2017). https:\/\/doi.org\/10.1016\/j.ic.2017.06.001","journal-title":"Inf. Comput."}],"container-title":["Lecture Notes in Computer Science","Treewidth, Kernels, and Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-42071-0_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,18]],"date-time":"2022-12-18T14:03:19Z","timestamp":1671372199000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-42071-0_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030420703","9783030420710"],"references-count":77,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-42071-0_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"20 April 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}