{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T20:55:33Z","timestamp":1725828933381},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662483497"},{"type":"electronic","value":"9783662483503"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"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":[[2015]]},"DOI":"10.1007\/978-3-662-48350-3_33","type":"book-chapter","created":{"date-parts":[[2015,9,1]],"date-time":"2015-09-01T01:40:34Z","timestamp":1441071634000},"page":"386-398","source":"Crossref","is-referenced-by-count":2,"title":["A Fixed Parameter Tractable Approximation Scheme for the Optimal Cut Graph of a Surface"],"prefix":"10.1007","author":[{"given":"Vincent","family":"Cohen-Addad","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arnaud","family":"de Mesmay","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,11,12]]},"reference":[{"key":"33_CR1","unstructured":"Bonsma, P.: Surface split decompositions and subgraph isomorphism in graphs on surfaces. In: Proc. of the Symp. on Theoretical Aspects of Computer Science, STACS 2012, pp. 531\u2013542 (2012)"},{"issue":"2","key":"33_CR2","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1007\/s00453-012-9662-2","volume":"68","author":"G. Borradaile","year":"2014","unstructured":"Borradaile, G., Demaine, E.D., Tazari, S.: Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs. Algorithmica\u00a068(2), 287\u2013311 (2014)","journal-title":"Algorithmica"},{"key":"33_CR3","doi-asserted-by":"crossref","unstructured":"Borradaile, G., Klein, P.N., Mathieu, C.: An O(nlogn) approximation scheme for Steiner tree in planar graphs. ACM Trans. on Algorithms\u00a05(3) (2009)","DOI":"10.1145\/1541885.1541892"},{"key":"33_CR4","doi-asserted-by":"crossref","unstructured":"Cohen-Addad, V., de Mesmay, A.: A fixed paramater tractable approximation scheme for the optimal cut graph of a surface (2015) (in preparation)","DOI":"10.1007\/978-3-662-48350-3_33"},{"key":"33_CR5","doi-asserted-by":"crossref","unstructured":"Demaine, E.D., Hajiaghayi, M., Kawarabayashi, K.I.: Contraction decomposition in h-minor-free graphs and algorithmic applications. In: Proc. of the ACM Symp. on Theory of Computing, STOC 2011, pp. 441\u2013450. ACM (2011)","DOI":"10.1145\/1993636.1993696"},{"key":"33_CR6","doi-asserted-by":"crossref","unstructured":"Demaine, E.D., Hajiaghayi, M., Mohar, B.: Approximation algorithms via contraction decomposition. Combinatorica, 533\u2013552 (2010)","DOI":"10.1007\/s00493-010-2341-5"},{"key":"33_CR7","unstructured":"Erickson, J.: Combinatorial optimization of cycles and bases. In: Zomorodian, A. (ed.) Computational Topology. Proc. of Symp. in Applied Mathematics, AMS (2012)"},{"issue":"1","key":"33_CR8","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/s00454-003-2948-z","volume":"31","author":"J. Erickson","year":"2004","unstructured":"Erickson, J., Har-Peled, S.: Optimally cutting a surface into a disk. Discrete & Computational Geometry\u00a031(1), 37\u201359 (2004)","journal-title":"Discrete & Computational Geometry"},{"issue":"4","key":"33_CR9","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1287\/moor.12.4.634","volume":"12","author":"R.E. Erickson","year":"1987","unstructured":"Erickson, R.E., Monma, C.L., Veinott Jr., A.F.: Send-and-split method for minimum-concave-cost network flows. Mathematics of Operations Research\u00a012(4), 634\u2013664 (1987)","journal-title":"Mathematics of Operations Research"},{"issue":"1","key":"33_CR10","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1002\/jgt.20219","volume":"55","author":"F.V. Fomin","year":"2007","unstructured":"Fomin, F.V., Thilikos, D.M.: On self duality of pathwidth in polyhedral graph embeddings. Journal of Graph Theory\u00a055(1), 42\u201354 (2007)","journal-title":"Journal of Graph Theory"},{"key":"33_CR11","unstructured":"Inkmann, T.: Tree-based decompositions of graphs on surfaces and applications to the Traveling Salesman Problem. Ph.D. thesis, Georgia Inst. of Technology (2007)"},{"issue":"1","key":"33_CR12","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1093\/comjnl\/bxm048","volume":"51","author":"D. Marx","year":"2008","unstructured":"Marx, D.: Parameterized complexity and approximation algorithms. The Computer Journal\u00a051(1), 60\u201378 (2008)","journal-title":"The Computer Journal"},{"issue":"3","key":"33_CR13","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1016\/j.jctb.2011.11.002","volume":"102","author":"F. Mazoit","year":"2012","unstructured":"Mazoit, F.: Tree-width of hypergraphs and surface duality. J. Comb. Theory, Ser. B\u00a0102(3), 671\u2013687 (2012)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"33_CR14","unstructured":"Mohar, B., Thomassen, C.: Graphs on surfaces. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press (2001)"},{"key":"33_CR15","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: Proceedings of Foundations of Computer Science (FOCS), pp. 276\u2013285 (2014)","DOI":"10.1109\/FOCS.2014.37"},{"issue":"2","key":"33_CR16","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/0095-8956(91)90061-N","volume":"52","author":"N. Robertson","year":"1991","unstructured":"Robertson, N., Seymour, P.: Graph minors. X. obstructions to tree-decomposition. J. Combin. Theory Ser. B\u00a052(2), 153\u2013190 (1991)","journal-title":"J. Combin. Theory Ser. B"},{"key":"33_CR17","doi-asserted-by":"crossref","unstructured":"Ru\u00e9, J., Sau, I., Thilikos, D.M.: Dynamic programming for graphs on surfaces. ACM Trans. Algorithms 10(2), 8:1\u20138:26 (2014)","DOI":"10.1145\/2556952"},{"key":"33_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1007\/3-540-40996-3_17","volume-title":"Algorithms and Computation","author":"D.M. Thilikos","year":"2000","unstructured":"Thilikos, D.M., Serna, M., Bodlaender, H.L.: Constructive linear time algorithms for small cutwidth and carving-width. In: Lee, D.T., Teng, S.-H. (eds.) ISAAC 2000. LNCS, vol.\u00a01969, pp. 192\u2013203. Springer, Heidelberg (2000)"},{"key":"33_CR19","unstructured":"Colin\u00a0de Verdi\u00e8re, \u00c9.: Topological algorithms for graphs on surfaces (2012), habilitation thesis. \n                    \n                      http:\/\/www.di.ens.fr\/~colin\/"},{"issue":"2","key":"33_CR20","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1145\/990002.990007","volume":"23","author":"Z. Wood","year":"2004","unstructured":"Wood, Z., Hoppe, H., Desbrun, M., Schr\u00f6der, P.: Removing excess topology from isosurfaces. ACM Transactions on Graphics\u00a023(2), 190\u2013208 (2004)","journal-title":"ACM Transactions on Graphics"}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA 2015"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-48350-3_33","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T20:21:10Z","timestamp":1559247670000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-48350-3_33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662483497","9783662483503"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-48350-3_33","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}