{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:01:58Z","timestamp":1725487318714},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540404934"},{"type":"electronic","value":"9783540450610"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-45061-0_66","type":"book-chapter","created":{"date-parts":[[2007,7,16]],"date-time":"2007-07-16T11:54:04Z","timestamp":1184586844000},"page":"845-856","source":"Crossref","is-referenced-by-count":2,"title":["Genus Characterizes the Complexity of Graph Problems: Some Tight Results"],"prefix":"10.1007","author":[{"given":"Jianer","family":"Chen","sequence":"first","affiliation":[]},{"given":"Iyad A.","family":"Kanj","sequence":"additional","affiliation":[]},{"given":"Ljubomir","family":"Perkovi\u0107","sequence":"additional","affiliation":[]},{"given":"Eric","family":"Sedgwick","sequence":"additional","affiliation":[]},{"given":"Ge","family":"Xia","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2003,6,18]]},"reference":[{"key":"66_CR1","first-page":"111","volume":"2136","author":"J. Alber","year":"2001","unstructured":"J. Alber, H. Fan, M. Fellows, H. Fernau, R. Niedermeier, F. Rosamond, and U. Stege, Refined search tree technique for dominating set on planar graphs, LNCS2136, (2001), pp. 111\u2013122.","journal-title":"LNCS"},{"key":"66_CR2","first-page":"261","volume":"2076","author":"J. Alber","year":"2001","unstructured":"J. Alber, H. Fernau, and R. Niedermeier, Parameterized complexity: exponential speedup for planar graph problems, LNCS2076, (2001), pp. 261\u2013272.","journal-title":"LNCS"},{"key":"66_CR3","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1145\/278298.278306","volume":"45","author":"S. Arora","year":"1998","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy, Proof verification and hardness of approximation problems, J. ACM45, (1998), pp. 501\u2013555.","journal-title":"J. ACM"},{"key":"66_CR4","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-58412-1","volume-title":"Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties","author":"G. Ausiello","year":"1999","unstructured":"G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi, Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer-Verlag, Berlin Heidelberg, 1999."},{"key":"66_CR5","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"B. Baker","year":"1994","unstructured":"B. Baker, Approximation algorithms for NP-complete problems on planar graphs, J. ACM41, (1994), pp. 153\u2013180.","journal-title":"J. ACM"},{"key":"66_CR6","unstructured":"L. Cai and D. Juedes, On the existence of subexponential-time parameterized algorithms, JCSS, to appear."},{"key":"66_CR7","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1016\/S0304-3975(96)00273-3","volume":"181","author":"J. Chen","year":"1987","unstructured":"J. Chen, Algorithmic graph embeddings, TCS181, (1987), pp. 247\u2013266.","journal-title":"TCS"},{"key":"66_CR8","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/S0020-0190(97)00203-2","volume":"61","author":"J. Chen","year":"1997","unstructured":"J. Chen, S. Kanchi, and A. Kanevsky, A note on approximating graph genus, Information Processing Letters61, (1997), pp. 317\u2013322.","journal-title":"Information Processing Letters"},{"key":"66_CR9","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1006\/jagm.2001.1186","volume":"41","author":"J. Chen","year":"2001","unstructured":"J. Chen, I. Kanj, and W. Jia, Vertex cover: further observations and further improvements, J. Algorithms41, (2001), pp. 280\u2013301.","journal-title":"J. Algorithms"},{"key":"66_CR10","first-page":"62","volume":"1017","author":"H. Djidjev","year":"1995","unstructured":"H. Djidjev and S. Venkatesan, Planarization of graphs embedded on surfaces, LNCS1017 (WG\u201995), (1995), pp. 62\u201372.","journal-title":"LNCS"},{"key":"66_CR11","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R. Downey","year":"1999","unstructured":"R. Downey and M. Fellows, Parameterized Complexity, Springer-Verlag, New York, 1999."},{"key":"66_CR12","first-page":"180","volume":"2368","author":"J. Ellis","year":"2002","unstructured":"J. Ellis, H. Fan, and M. Fellows, The dominating set problem is fixed parameter tractable for graphs of bounded genus, LNCS2368, (2002), pp. 180\u2013189.","journal-title":"LNCS"},{"key":"66_CR13","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"M. Garey","year":"1979","unstructured":"M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, Freeman, San Francisco, 1979."},{"key":"66_CR14","volume-title":"Topological Graph Theory","author":"J. Gross","year":"1987","unstructured":"J. Gross and T. Tucker, Topological Graph Theory, Wiley-Interscience, New York, 1987."},{"key":"66_CR15","first-page":"512","volume":"63","author":"R. Impagliazzo","year":"2001","unstructured":"R. Impagliazzo, R. Paturi, and F. Zane, Which problems have strongly exponential complexity? JCSS63, (2001), pp. 512\u2013530.","journal-title":"JCSS"},{"key":"66_CR16","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1137\/0209046","volume":"9","author":"R. Lipton","year":"1980","unstructured":"R. Lipton and R. Tarjan, Applications of a planar separator theorem, SIAM Journal on Computing9, (1980), pp. 615\u2013627.","journal-title":"SIAM Journal on Computing"},{"key":"66_CR17","first-page":"425","volume":"43","author":"C. Papadimitriou","year":"1991","unstructured":"C. Papadimitriou and M. Yannakakis, Optimization, approximation and complexity classes, JCSS43, (1991), pp. 425\u2013440.","journal-title":"JCSS"},{"key":"66_CR18","doi-asserted-by":"publisher","first-page":"568","DOI":"10.1016\/0196-6774(89)90006-0","volume":"10","author":"C. Thomassen","year":"1989","unstructured":"C. Thomassen, The graph genus problem is NP-complete, J. Algorithms10, (1989), pp. 568\u2013576.","journal-title":"J. Algorithms"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45061-0_66","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,17]],"date-time":"2019-02-17T18:44:20Z","timestamp":1550429060000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45061-0_66"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540404934","9783540450610"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/3-540-45061-0_66","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2003]]}}}