{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,15]],"date-time":"2024-09-15T14:11:04Z","timestamp":1726409464125},"publisher-location":"Cham","reference-count":21,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319135236"},{"type":"electronic","value":"9783319135243"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"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":[[2014]]},"DOI":"10.1007\/978-3-319-13524-3_6","type":"book-chapter","created":{"date-parts":[[2014,12,2]],"date-time":"2014-12-02T17:51:38Z","timestamp":1417542698000},"page":"63-74","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The Role of Planarity in Connectivity Problems Parameterized by Treewidth"],"prefix":"10.1007","author":[{"given":"Julien","family":"Baste","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ignasi","family":"Sau","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,12,3]]},"reference":[{"key":"6_CR1","doi-asserted-by":"crossref","unstructured":"Baste, J., Sau, I.: The role of planarity in connectivity problems parameterized by treewidth. CoRR, abs\/1312.2889 (2013)","DOI":"10.1007\/978-3-319-13524-3_6"},{"key":"6_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1007\/978-3-642-39206-1_17","volume-title":"Automata, Languages, and Programming","author":"HL Bodlaender","year":"2013","unstructured":"Bodlaender, H.L., Cygan, M., Kratsch, S., Nederlof, J.: Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part I. LNCS, vol. 7965, pp. 196\u2013207. Springer, Heidelberg (2013)"},{"issue":"1","key":"6_CR3","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inform. Comput. 85(1), 12\u201375 (1990)","journal-title":"Inform. Comput."},{"key":"6_CR4","doi-asserted-by":"crossref","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: Proceeding of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 150\u2013159. IEEE Computer Society (2011)","DOI":"10.1109\/FOCS.2011.23"},{"key":"6_CR5","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1007\/s10878-005-1778-8","volume":"9","author":"VG Deineko","year":"2005","unstructured":"Deineko, V.G., Steiner, G., Xue, Z.: Robotic-cell scheduling: special polynomially solvable cases of the traveling salesman problem on permuted monge matrices. J. Comb. Optim. 9, 381\u2013399 (2005)","journal-title":"J. Comb. Optim."},{"key":"6_CR6","volume-title":"Graph Theory","author":"R Diestel","year":"2005","unstructured":"Diestel, R.: Graph Theory, 3rd edn. Springer, New York (2005)","edition":"3"},{"key":"6_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1007\/11785293_18","volume-title":"Algorithm Theory \u2013 SWAT 2006","author":"F Dorn","year":"2006","unstructured":"Dorn, F., Fomin, F.V., Thilikos, D.M.: Fast subexponential algorithm for non-local problems on graphs of bounded genus. In: Arge, L., Freivalds, R. (eds.) SWAT 2006. LNCS, vol. 4059, pp. 172\u2013183. Springer, Heidelberg (2006)"},{"issue":"5","key":"6_CR8","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. Syst. Sci. 78(5), 1606\u20131622 (2012)","journal-title":"J. Syst. Sci."},{"issue":"3","key":"6_CR9","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)","journal-title":"Algorithmica"},{"key":"6_CR10","series-title":"Theoretical Computer Science","volume-title":"Parameterized Complexity Theory","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Theoretical Computer Science. Springer, Berlin (2006)"},{"key":"6_CR11","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S.: Efficient Computation of Representative Sets with Applications in Parameterized and Exact Algorithms. In: Proceeding of SODA\u201914. CoRR, abs\/1304.4626 (2013)","DOI":"10.1137\/1.9781611973402.10"},{"issue":"4","key":"6_CR12","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."},{"key":"6_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"282","DOI":"10.1007\/3-540-36379-3_25","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"T Kloks","year":"2002","unstructured":"Kloks, T., Lee, C.M., Liu, J.: New algorithms for $$k$$ -face cover, $$k$$ -feedback vertex set, and $$k$$ -disjoint cycles on plane and planar graphs. In: Ku\u010dera, L. (ed.) WG 2002. LNCS, vol. 2573, pp. 282\u2013295. Springer, Heidelberg (2002)"},{"key":"6_CR14","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Known algorithms on graphs of bounded treewidth are probably optimal. In: Proceeding of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 777\u2013789 (2011)","DOI":"10.1137\/1.9781611973082.61"},{"key":"6_CR15","first-page":"41","volume":"105","author":"D Lokshtanov","year":"2011","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Lower bounds based on the exponential time hypothesis. Bull. EATCS 105, 41\u201372 (2011)","journal-title":"Bull. EATCS"},{"key":"6_CR16","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Slightly superexponential parameterized problems. In: Proceeding of the 22nd Annual ACM-SIAM Symposium on Discrete algorithms (SODA), pp. 760\u2013776 (2011)","DOI":"10.1137\/1.9781611973082.60"},{"key":"6_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"520","DOI":"10.1007\/978-3-642-22993-0_47","volume-title":"Mathematical Foundations of Computer Science 2011","author":"M Pilipczuk","year":"2011","unstructured":"Pilipczuk, M.: Problems parameterized by treewidth tractable in single exponential time: a logical approach. In: Murlak, F., Sankowski, P. (eds.) MFCS 2011. LNCS, vol. 6907, pp. 520\u2013531. Springer, Heidelberg (2011)"},{"issue":"3","key":"6_CR18","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 7(3), 309\u2013322 (1986)","journal-title":"J. Algorithms"},{"key":"6_CR19","unstructured":"Ru\u00e9, J., Sau, I., Thilikos, D.M.: Dynamic programming for graphs on surfaces. In: Short Version in the Proceeding of ICALP\u201910 in ACM Transactions on Algorithms (TALG). CoRR, abs\/1104.2486 (2011)"},{"key":"6_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-32241-9_1","volume-title":"Computing and Combinatorics","author":"B Bhattacharya","year":"2012","unstructured":"Bhattacharya, B., Kameda, T.: A linear time algorithm for computing minmax regret 1-median on a tree. In: Gudmundsson, J., Mestre, J., Viglas, T. (eds.) COCOON 2012. LNCS, vol. 7434, pp. 1\u201312. Springer, Heidelberg (2012)"},{"key":"6_CR21","unstructured":"Scheffler, P.: A practical linear time algorithm for disjoint paths in graphs with bounded tree-width. Fachbereich 3 Mathematik, Technical Report 396\/1994, FU Berlin (1994)"}],"container-title":["Lecture Notes in Computer Science","Parameterized and Exact Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-13524-3_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,23]],"date-time":"2022-04-23T18:51:20Z","timestamp":1650739880000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-13524-3_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319135236","9783319135243"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-13524-3_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]},"assertion":[{"value":"3 December 2014","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}