{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T06:20:57Z","timestamp":1725603657454},"publisher-location":"Berlin, Heidelberg","reference-count":37,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642237188"},{"type":"electronic","value":"9783642237195"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"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":[[2011]]},"DOI":"10.1007\/978-3-642-23719-5_31","type":"book-chapter","created":{"date-parts":[[2011,8,30]],"date-time":"2011-08-30T09:14:33Z","timestamp":1314695673000},"page":"358-369","source":"Crossref","is-referenced-by-count":2,"title":["Fast Sub-exponential Algorithms and Compactness in Planar Graphs"],"prefix":"10.1007","author":[{"given":"Dimitrios M.","family":"Thilikos","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"31_CR1","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/s00453-001-0116-5","volume":"33","author":"J. Alber","year":"2002","unstructured":"Alber, J., Bodlaender, H.L., Fernau, H., Kloks, T., Niedermeier, R.: Fixed parameter algorithms for dominating set and related problems on planar graphs. Algorithmica\u00a033, 461\u2013493 (2002)","journal-title":"Algorithmica"},{"key":"31_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/978-3-642-02927-1_6","volume-title":"Automata, Languages and Programming","author":"N. Alon","year":"2009","unstructured":"Alon, N., Lokshtanov, D., Saurabh, S.: Fast FAST. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009. LNCS, vol.\u00a05555, pp. 49\u201358. Springer, Heidelberg (2009)"},{"key":"31_CR3","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1137\/S0895480191198768","volume":"7","author":"N. Alon","year":"1994","unstructured":"Alon, N., Seymour, P., Thomas, R.: Planar separators. SIAM J. Discrete Math.\u00a07, 184\u2013193 (1994)","journal-title":"SIAM J. Discrete Math."},{"key":"31_CR4","doi-asserted-by":"publisher","first-page":"629","DOI":"10.1109\/FOCS.2009.46","volume-title":"50th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009)","author":"H.L. Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Fomin, F.V., Lokshtanov, D., Penninkx, E., Saurabh, S., Thilikos, D.M.: (Meta) Kernelization. In: 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009), pp. 629\u2013638. IEEE, Los Alamitos (2009)"},{"key":"31_CR5","doi-asserted-by":"publisher","first-page":"789","DOI":"10.1016\/S0022-0000(03)00074-6","volume":"67","author":"L. Cai","year":"2003","unstructured":"Cai, L., Juedes, D.: On the existence of subexponential parameterized algorithms. Journal of Computer and System Sciences\u00a067, 789\u2013807 (2003)","journal-title":"Journal of Computer and System Sciences"},{"key":"31_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"845","DOI":"10.1007\/3-540-45061-0_66","volume-title":"Automata, Languages and Programming","author":"J. Chen","year":"2003","unstructured":"Chen, J., Kanj, I., Perkovic, L., Sedgwick, E., Xia, G.: Genus characterizes the complexity of graph problems: some tight results. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol.\u00a02719, pp. 845\u2013856. Springer, Heidelberg (2003)"},{"key":"31_CR7","doi-asserted-by":"publisher","first-page":"292","DOI":"10.1093\/comjnl\/bxm033","volume":"51","author":"E. Demaine","year":"2007","unstructured":"Demaine, E., Hajiaghayi, M.: The bidimensionality theory and its algorithmic applications. The Computer Journal\u00a051, 292\u2013302 (2007)","journal-title":"The Computer Journal"},{"key":"31_CR8","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1137\/S0895480103433410","volume":"18","author":"E.D. Demaine","year":"2005","unstructured":"Demaine, E.D., Fomin, F.V., Hajiaghayi, M., Thilikos, D.M.: Bidimensional parameters and local treewidth. SIAM J. Discrete Math.\u00a018, 501\u2013511 (2005)","journal-title":"SIAM J. Discrete Math."},{"key":"31_CR9","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1145\/1077464.1077468","volume":"1","author":"E.D. Demaine","year":"2005","unstructured":"Demaine, E.D., Fomin, F.V., Hajiaghayi, M., Thilikos, D.M.: Fixed-parameter algorithms for (k,r)-center in planar graphs and map graphs. ACM Trans. Algorithms\u00a01, 33\u201347 (2005)","journal-title":"ACM Trans. Algorithms"},{"key":"31_CR10","doi-asserted-by":"publisher","first-page":"866","DOI":"10.1145\/1101821.1101823","volume":"52","author":"E.D. Demaine","year":"2005","unstructured":"Demaine, E.D., Fomin, F.V., Hajiaghayi, M., Thilikos, D.M.: Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs. J. Assoc. Comput. Mach.\u00a052, 866\u2013893 (2005)","journal-title":"J. Assoc. Comput. Mach."},{"key":"31_CR11","first-page":"590","volume-title":"Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"E.D. Demaine","year":"2005","unstructured":"Demaine, E.D., Hajiaghayi, M.: Bidimensionality: new connections between FPT algorithms and PTASs. In: Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 590\u2013601. ACM, New York (2005) (electronic)"},{"key":"31_CR12","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/s00453-004-1125-y","volume":"41","author":"E.D. Demaine","year":"2005","unstructured":"Demaine, E.D., Hajiaghayi, M., Thilikos, D.M.: Exponential speedup of fixed-parameter algorithms for classes of graphs excluding single-crossing graphs as minors. Algorithmica\u00a041, 245\u2013267 (2005)","journal-title":"Algorithmica"},{"key":"31_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1007\/11841036_27","volume-title":"Algorithms \u2013 ESA 2006","author":"F. Dorn","year":"2006","unstructured":"Dorn, F.: Dynamic Programming and Fast Matrix Multiplication. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol.\u00a04168, pp. 280\u2013291. Springer, Heidelberg (2006)"},{"key":"31_CR14","unstructured":"Dorn, F., Fomin, F.V., Lokshtanov, D., Raman, V., Saurabh, S.: Beyond bidimensionality: Parameterized subexponential algorithms on directed graphs. In: 27th International Symposium on Theoretical Aspects of Computer Science (STACS 2010). LIPIcs, vol.\u00a05, pp. 251\u2013262. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2010)"},{"key":"31_CR15","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/j.cosrev.2008.02.004","volume":"2","author":"F. Dorn","year":"2008","unstructured":"Dorn, F., Fomin, F.V., Thilikos, D.M.: Subexponential parameterized algorithms. Computer Science Review\u00a02, 29\u201339 (2008)","journal-title":"Computer Science Review"},{"key":"31_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1007\/3-540-36379-3_17","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"H. Fernau","year":"2002","unstructured":"Fernau, H.: Graph Separator Algorithms: A Refined Analysis. In: Ku\u010dera, L. (ed.) WG 2002. LNCS, vol.\u00a02573, pp. 186\u2013197. Springer, Heidelberg (2002)"},{"key":"31_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"488","DOI":"10.1007\/978-3-540-28629-5_37","volume-title":"Mathematical Foundations of Computer Science 2004","author":"H. Fernau","year":"2004","unstructured":"Fernau, H., Juedes, D.: A Geometric Approach to Parameterized Algorithms for Domination Problems on Planar Graphs. In: Fiala, J., Koubek, V., Kratochv\u00edl, J. (eds.) MFCS 2004. LNCS, vol.\u00a03153, pp. 488\u2013499. Springer, Heidelberg (2004)"},{"key":"31_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"706","DOI":"10.1007\/978-3-642-04128-0_63","volume-title":"Algorithms - ESA 2009","author":"F.V. Fomin","year":"2009","unstructured":"Fomin, F.V., Golovach, P., Thilikos, D.M.: Contraction bidimensionality: The accurate picture. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol.\u00a05757, pp. 706\u2013717. Springer, Heidelberg (2009)"},{"key":"31_CR19","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Raman, V., Saurabh, S.: Bidimensionality and EPTAS. In: 22st ACM\u2013SIAM Symposium on Discrete Algorithms (SODA 2011), pp. 748\u2013759. ACM-SIAM, San Francisco (2011)","DOI":"10.1137\/1.9781611973082.59"},{"key":"31_CR20","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S., Thilikos, D.M.: Bidimensionality and kernels. In: 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010), Austin, Texas, pp. 503\u2013510. ACM-SIAM (2010)","DOI":"10.1137\/1.9781611973075.43"},{"key":"31_CR21","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1137\/S0097539702419649","volume":"36","author":"F.V. Fomin","year":"2006","unstructured":"Fomin, F.V., Thilikos, D.M.: ominating sets in planar graphs: branch-width and exponential speed-up. SIAM J. Comput.\u00a036, 281\u2013309 (2006) (electronic)","journal-title":"SIAM J. Comput."},{"key":"31_CR22","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1002\/jgt.20121","volume":"51","author":"F.V. Fomin","year":"2006","unstructured":"Fomin, F.V., Thilikos, D.M.: New upper bounds on the decomposability of planar graphs. Journal of Graph Theory\u00a051, 53\u201381 (2006)","journal-title":"Journal of Graph Theory"},{"key":"31_CR23","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Villanger, Y.: Subexponential parameterized algorithm for minimum fill-in. CoRR, abs\/1104.2230 (2011)","DOI":"10.1137\/1.9781611973099.138"},{"key":"31_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1367064.1367070","volume":"4","author":"Q.-P. Gu","year":"2008","unstructured":"Gu, Q.-P., Tamaki, H.: Optimal branch decomposition of planar graphs in O(n 3) time. ACM Trans. Algorithms\u00a04, 1\u201313 (2008)","journal-title":"ACM Trans. Algorithms"},{"key":"31_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-3-642-17514-5_8","volume-title":"Algorithms and Computation","author":"Q.-P. Gu","year":"2010","unstructured":"Gu, Q.-P., Tamaki, H.: Improved Bounds on the Planar Branchwidth with Respect to the Largest Grid Minor Size. In: Cheong, O., Chwa, K.-Y., Park, K. (eds.) ISAAC 2010, Part II. LNCS, vol.\u00a06507, pp. 85\u201396. Springer, Heidelberg (2010)"},{"key":"31_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1007\/978-3-540-73420-8_34","volume-title":"Automata, Languages and Programming","author":"J. Guo","year":"2007","unstructured":"Guo, J., Niedermeier, R.: Linear Problem Kernels for NP-Hard Problems on Planar Graphs. In: Arge, L., Cachin, C., Jurdzi\u0144ski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol.\u00a04596, pp. 375\u2013386. Springer, Heidelberg (2007)"},{"key":"31_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1007\/3-540-45687-2_33","volume-title":"Mathematical Foundations of Computer Science 2002","author":"I.A. Kanj","year":"2002","unstructured":"Kanj, I., Perkovi\u0107, L.: Improved Parameterized Algorithms for Planar Dominating Set. In: Diks, K., Rytter, W. (eds.) MFCS 2002. LNCS, vol.\u00a02420, pp. 399\u2013410. Springer, Heidelberg (2002)"},{"key":"31_CR28","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.\u00a02573, pp. 282\u2013295. Springer, Heidelberg (2002)"},{"key":"31_CR29","doi-asserted-by":"crossref","unstructured":"Koutsonas, A., Thilikos, D.: Planar feedback vertex set and face cover: Combinatorial bounds and subexponential algorithms. Algorithmica, 1\u201317 (2010)","DOI":"10.1007\/s00453-010-9390-4"},{"key":"31_CR30","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Known algorithms on graphs of bounded treewidth are probably optimal. In: 22st ACM\u2013SIAM Symposium on Discrete Algorithms (SODA 2011), pp. 777\u2013789. ACM-SIAM, San Francisco, California (2011)","DOI":"10.1137\/1.9781611973082.61"},{"key":"31_CR31","doi-asserted-by":"crossref","unstructured":"Mazoit, F., Thomass\u00e9, S.: Branchwidth of graphic matroids. In: Surveys in combinatorics 2007. London Math. Soc. Lecture Note Ser., vol.\u00a0346, pp. 275\u2013286. Cambridge Univ. Press, Cambridge (2007)","DOI":"10.1017\/CBO9780511666209.010"},{"key":"31_CR32","doi-asserted-by":"crossref","unstructured":"Pilipczuk, M.: Problems parameterized by treewidth tractable in single exponential time: a logical approach. Tech. Rep. arXiv:1104.3057, Cornell University (April 2011)","DOI":"10.1007\/978-3-642-22993-0_47"},{"key":"31_CR33","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. Combin. Theory Ser. B\u00a062, 323\u2013348 (1994)","journal-title":"J. Combin. Theory Ser. B"},{"key":"31_CR34","doi-asserted-by":"crossref","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. X. Obstructions to tree-decomposition. J. Combin. Theory Ser. B\u00a052, 153\u2013190 (1991)","DOI":"10.1016\/0095-8956(91)90061-N"},{"key":"31_CR35","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, 217\u2013241 (1994)","journal-title":"Combinatorica"},{"key":"31_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"641","DOI":"10.1007\/978-3-642-15155-2_56","volume-title":"Mathematical Foundations of Computer Science 2010","author":"S. Tazari","year":"2010","unstructured":"Tazari, S.: Faster approximation schemes and parameterized algorithms on H-minor-free and odd-minor-free graphs. In: Hlin\u011bn\u00fd, P., Ku\u010dera, A. (eds.) MFCS 2010. LNCS, vol.\u00a06281, pp. 641\u2013652. Springer, Heidelberg (2010)"},{"key":"31_CR37","doi-asserted-by":"crossref","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)","DOI":"10.1007\/978-3-642-04128-0_51"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2011"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-23719-5_31","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,14]],"date-time":"2019-06-14T12:08:24Z","timestamp":1560514104000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-23719-5_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642237188","9783642237195"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-23719-5_31","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}