{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T16:01:01Z","timestamp":1725897661871},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642322402"},{"type":"electronic","value":"9783642322419"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-32241-9_8","type":"book-chapter","created":{"date-parts":[[2012,8,13]],"date-time":"2012-08-13T15:12:12Z","timestamp":1344870732000},"page":"86-97","source":"Crossref","is-referenced-by-count":3,"title":["Dynamic Programming for H-minor-free Graphs"],"prefix":"10.1007","author":[{"given":"Juanjo","family":"Ru\u00e9","sequence":"first","affiliation":[]},{"given":"Ignasi","family":"Sau","sequence":"additional","affiliation":[]},{"given":"Dimitrios M.","family":"Thilikos","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"8_CR1","doi-asserted-by":"crossref","unstructured":"Andrews, G.: The Theory of Partitions. Cambridge University Press (1984)","DOI":"10.1017\/CBO9780511608650"},{"issue":"1","key":"8_CR2","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1007\/BF01934985","volume":"25","author":"S. Arnborg","year":"1985","unstructured":"Arnborg, S.: Efficient algorithms for combinatorial problems on graphs with bounded decomposability \u2013 a survey. BIT\u00a025(1), 2\u201323 (1985)","journal-title":"BIT"},{"key":"8_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1007\/978-3-540-85363-3_23","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"V. Arvind","year":"2008","unstructured":"Arvind, V., Mukhopadhyay, P.: Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size. In: Goel, A., Jansen, K., Rolim, J.D.P., Rubinfeld, R. (eds.) APPROX and RANDOM 2008. LNCS, vol.\u00a05171, pp. 276\u2013289. Springer, Heidelberg (2008)"},{"key":"8_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/3-540-19488-6_110","volume-title":"Automata, Languages and Programming","author":"H.L. Bodlaender","year":"1988","unstructured":"Bodlaender, H.L.: Dynamic Programming on Graphs with Bounded Treewidth. In: Lepist\u00f6, T., Salomaa, A. (eds.) ICALP 1988. LNCS, vol.\u00a0317, pp. 105\u2013118. Springer, Heidelberg (1988)"},{"key":"8_CR5","unstructured":"Bonsma, P.: Surface split decompositions and subgraph isomorphism in graphs on surfaces. CoRR, abs\/1109.4554 (2011), to appear in the Proc. of STACS 2012"},{"key":"8_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1007\/3-540-50728-0_34","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"B. Courcelle","year":"1989","unstructured":"Courcelle, B.: The Monadic Second-Order Logic of Graphs: Definable Sets of Finite Graphs. In: van Leeuwen, J. (ed.) WG 1988. LNCS, vol.\u00a0344, pp. 30\u201353. Springer, Heidelberg (1989)"},{"key":"8_CR7","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: Proc. of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 150\u2013159 (2011)","DOI":"10.1109\/FOCS.2011.23"},{"issue":"6","key":"8_CR8","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.T., Thilikos, D.M.: Subexponential Parameterized Algorithms on Graphs of Bounded Genus and H-Minor-Free Graphs. Journal of the ACM\u00a052(6), 866\u2013893 (2005)","journal-title":"Journal of the ACM"},{"key":"8_CR9","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.\u00a04059, pp. 172\u2013183. Springer, Heidelberg (2006)"},{"key":"8_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/978-3-540-73420-8_4","volume-title":"Automata, Languages and Programming","author":"F. Dorn","year":"2007","unstructured":"Dorn, F., Fomin, F.V., Thilikos, D.M.: Subexponential Parameterized Algorithms. In: Arge, L., Cachin, C., Jurdzi\u0144ski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol.\u00a04596, pp. 15\u201327. Springer, Heidelberg (2007)"},{"key":"8_CR11","unstructured":"Dorn, F., Fomin, F.V., Thilikos, D.M.: Catalan Structures and Dynamic Programming in H-minor-free Graphs. In: Proc. of the 19th Annual ACM-SIAM Symposium on Discrete algorithms (SODA), pp. 631\u2013640 (2008)"},{"issue":"3","key":"8_CR12","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\u00a058(3), 790\u2013810 (2010)","journal-title":"Algorithmica"},{"issue":"5","key":"8_CR13","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1006\/eujc.2002.0582","volume":"23","author":"A. Dress","year":"2002","unstructured":"Dress, A., Koolen, J.H., Moulton, V.: On line arrangements in the hyperbolic plane. European Journal of Combinatorics\u00a023(5), 549\u2013557 (2002)","journal-title":"European Journal of Combinatorics"},{"issue":"1","key":"8_CR14","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/j.jcta.2005.01.009","volume":"112","author":"J. Jonsson","year":"2005","unstructured":"Jonsson, J.: Generalized triangulations and diagonal-free subsets of stack polyominoes. Journal of Combinatorial Theory, Series A\u00a0112(1), 117\u2013142 (2005)","journal-title":"Journal of Combinatorial Theory, Series A"},{"key":"8_CR15","doi-asserted-by":"crossref","unstructured":"Kawarabayashi, K.-I., Wollan, P.: A simpler algorithm and shorter proof for the graph minor decomposition. In: Proc. of the 43rd ACM Symposium on Theory of Computing (STOC), pp. 451\u2013458 (2011)","DOI":"10.1145\/1993636.1993697"},{"key":"8_CR16","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Slightly Superexponential Parameterized Problems. In: Proc. of the 22nd annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 760\u2013776 (2011)","DOI":"10.1137\/1.9781611973082.60"},{"key":"8_CR17","doi-asserted-by":"crossref","unstructured":"Mohar, B., Thomassen, C.: Graphs on surfaces. John Hopkins University Press (2001)","DOI":"10.56021\/9780801866890"},{"issue":"1","key":"8_CR18","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BF02579206","volume":"7","author":"K. Mulmuley","year":"1987","unstructured":"Mulmuley, K., Vazirani, U.V., Vazirani, V.V.: Matching is as easy as matrix inversion. Combinatorica\u00a07(1), 105\u2013113 (1987)","journal-title":"Combinatorica"},{"issue":"2","key":"8_CR19","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1016\/S0304-3975(99)00199-1","volume":"235","author":"T. Nakamigawa","year":"2000","unstructured":"Nakamigawa, T.: A generalization of diagonal flips in a convex polygon. Theoretical Computer Science\u00a0235(2), 271\u2013282 (2000)","journal-title":"Theoretical Computer Science"},{"key":"8_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/jctb.1999.1919","volume":"77","author":"N. Robertson","year":"1999","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XVI. Excluding a Non-planar Graph. Journal of Combinatorial Theory, Series B\u00a077, 1\u201327 (1999)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"8_CR21","unstructured":"Ru\u00e9, J., Sau, I., Thilikos, D.M.: Asymptotic enumeration of non-crossing partitions on surfaces. In: CoRR, abs\/1104.2477 a preliminary version appeared in the Proc. of ICALP (2011), Last version, http:\/\/www.lirmm.fr\/~sau\/Pubs\/RST11NCP.pdf"},{"key":"8_CR22","unstructured":"Ru\u00e9, J., Sau, I., Thilikos, D.M.: Dynamic programming for graphs on surfaces. CoRR, abs\/1104.2486 (2011), to appear in ACM Transactions on Algorithms (TALG), last version available at, http:\/\/www.lirmm.fr\/~sau\/Pubs\/RST12TALG.pdf"},{"key":"8_CR23","doi-asserted-by":"crossref","unstructured":"Ru\u00e9, J., Sau, I., Thilikos, D.M.: Dynamic Programming for H-minor-free Graphs (2012), http:\/\/www.lirmm.fr\/~sau\/Pubs\/RSTminor12.pdf","DOI":"10.1007\/978-3-642-32241-9_8"},{"issue":"2","key":"8_CR24","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(2), 217\u2013241 (1994)","journal-title":"Combinatorica"},{"key":"8_CR25","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/j.tcs.2011.09.014","volume":"417","author":"S. Tazari","year":"2012","unstructured":"Tazari, S.: Faster approximation schemes and parameterized algorithms on (odd-) H-minor-free graphs. Theoretical Computer Science\u00a0417, 95\u2013107 (2012)","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-32241-9_8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,25]],"date-time":"2023-06-25T09:05:17Z","timestamp":1687683917000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-32241-9_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642322402","9783642322419"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-32241-9_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}