{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T13:37:57Z","timestamp":1725543477625},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540357537"},{"type":"electronic","value":"9783540357551"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11785293_18","type":"book-chapter","created":{"date-parts":[[2006,6,26]],"date-time":"2006-06-26T05:24:10Z","timestamp":1151299450000},"page":"172-183","source":"Crossref","is-referenced-by-count":17,"title":["Fast Subexponential Algorithm for Non-local Problems on Graphs of Bounded Genus"],"prefix":"10.1007","author":[{"given":"Frederic","family":"Dorn","sequence":"first","affiliation":[]},{"given":"Fedor V.","family":"Fomin","sequence":"additional","affiliation":[]},{"given":"Dimitrios M.","family":"Thilikos","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"18_CR1","doi-asserted-by":"crossref","unstructured":"De\u012dneko, V.G., Klinz, B., Woeginger, G.J.: Exact algorithms for the Hamiltonian cycle problem in planar graphs. Operations Research Letters (to appear, 2006)","DOI":"10.1016\/j.orl.2005.04.013"},{"key":"18_CR2","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 graphs of bounded genus and H-minor-free graphs. Journal of the ACM\u00a052, 866\u2013893 (2005)","journal-title":"Journal of the ACM"},{"key":"18_CR3","first-page":"590","volume-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005)","author":"E.D. Demaine","year":"2005","unstructured":"Demaine, E.D., Hajiaghayi, M.: Bidimensionality: new connections between FPT algorithms and PTASs. In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), pp. 590\u2013601. ACM-SIAM, New York (2005)"},{"key":"18_CR4","doi-asserted-by":"crossref","unstructured":"Dorn, F., Fomin, F.V., Thilikos, D.M.: Fast subexponential algorithm for non-local problems on graphs of bounded genus (manuscript, 2006), http:\/\/www.ii.uib.no\/publikasjoner\/texrap\/pdf\/2006-320.pdf","DOI":"10.1007\/11785293_18"},{"key":"18_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/11561071_11","volume-title":"Algorithms \u2013 ESA 2005","author":"F. Dorn","year":"2005","unstructured":"Dorn, F., Penninkx, E., Bodlaender, H., Fomin, F.V.: Efficient Exact Algorithms on Planar Graphs: Exploiting Sphere Cut Branch Decompositions. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol.\u00a03669, pp. 95\u2013106. Springer, Heidelberg (2005)"},{"key":"18_CR6","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":"18_CR7","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1016\/0196-6774(84)90019-1","volume":"5","author":"J.R. Gilbert","year":"1984","unstructured":"Gilbert, J.R., Hutchinson, J.P., Tarjan, R.E.: A separator theorem for graphs of bounded genus. Journal of Algorithms\u00a05, 391\u2013407 (1984)","journal-title":"Journal of Algorithms"},{"key":"18_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/11523468_31","volume-title":"Automata, Languages and Programming","author":"Q.-P. Gu","year":"2005","unstructured":"Gu, Q.-P., Tamaki, H.: Optimal branch-decomposition of planar graphs in O(n 3) time. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 373\u2013384. Springer, Heidelberg (2005)"},{"key":"18_CR9","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"R.J. Lipton","year":"1979","unstructured":"Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM J. Appl. Math.\u00a036, 177\u2013189 (1979)","journal-title":"SIAM J. Appl. Math."},{"key":"18_CR10","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1137\/0209046","volume":"9","author":"R.J. Lipton","year":"1980","unstructured":"Lipton, R.J., Tarjan, R.E.: Applications of a planar separator theorem. SIAM J. Comput.\u00a09, 615\u2013627 (1980)","journal-title":"SIAM J. Comput."},{"key":"18_CR11","series-title":"Johns Hopkins Studies in the Mathematical Sciences","doi-asserted-by":"crossref","DOI":"10.56021\/9780801866890","volume-title":"Graphs on surfaces","author":"B. Mohar","year":"2001","unstructured":"Mohar, B., Thomassen, C.: Graphs on surfaces. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore (2001)"},{"key":"18_CR12","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1016\/0095-8956(88)90070-6","volume":"45","author":"N. Robertson","year":"1988","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. VII. Disjoint paths on a surface. J. Combin. Theory Ser. B\u00a045, 212\u2013254 (1988)","journal-title":"J. Combin. Theory Ser. B"},{"key":"18_CR13","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":"18_CR14","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/0095-8956(90)90115-G","volume":"48","author":"C. Thomassen","year":"1990","unstructured":"Thomassen, C.: Embeddings of graphs with no short noncontractible cycles. J. Combin. Theory Ser. B\u00a048, 155\u2013177 (1990)","journal-title":"J. Combin. Theory Ser. B"},{"key":"18_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/3-540-36478-1_17","volume-title":"Combinatorial Optimization - Eureka, You Shrink!","author":"G. Woeginger","year":"2003","unstructured":"Woeginger, G.: Exact algorithms for NP-hard problems: A survey. In: J\u00fcnger, M., Reinelt, G., Rinaldi, G. (eds.) Combinatorial Optimization - Eureka, You Shrink! LNCS, vol.\u00a02570, pp. 185\u2013207. Springer, Heidelberg (2003)"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2013 SWAT 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11785293_18.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,7]],"date-time":"2023-05-07T20:47:56Z","timestamp":1683492476000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11785293_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540357537","9783540357551"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/11785293_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}