{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T10:31:46Z","timestamp":1725532306661},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642020162"},{"type":"electronic","value":"9783642020179"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-02017-9_20","type":"book-chapter","created":{"date-parts":[[2009,5,11]],"date-time":"2009-05-11T15:38:06Z","timestamp":1242056286000},"page":"168-177","source":"Crossref","is-referenced-by-count":0,"title":["On Parameterized Exponential Time Complexity"],"prefix":"10.1007","author":[{"given":"Jianer","family":"Chen","sequence":"first","affiliation":[]},{"given":"Iyad A.","family":"Kanj","sequence":"additional","affiliation":[]},{"given":"Ge","family":"Xia","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"20_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., Ferneau, H., Niedermeier, R.: Fixed parameter algorithms for Dominating Set and related problems on planar graphs. Algorithmica\u00a033, 461\u2013493 (2002)","journal-title":"Algorithmica"},{"key":"20_CR2","first-page":"27","volume":"25","author":"R. Bar-Yehuda","year":"1985","unstructured":"Bar-Yehuda, R., Even, S.: A local-ratio theorem for approximating the weighted vertex cover problem. Annals of Discrete Mathematics\u00a025, 27\u201346 (1985)","journal-title":"Annals of Discrete Mathematics"},{"key":"20_CR3","doi-asserted-by":"publisher","first-page":"560","DOI":"10.1137\/0222038","volume":"22","author":"J. Buss","year":"1993","unstructured":"Buss, J., Goldsmith, J.: Nondeterminism within P. SIAM Journal on Computing\u00a022, 560\u2013572 (1993)","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"20_CR4","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(4), 789\u2013807 (2003)","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"20_CR5","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1016\/j.ic.2005.05.001","volume":"201","author":"J. Chen","year":"2005","unstructured":"Chen, J., Chor, B., Fellows, M.R., Huang, X., Juedes, D.W., Kanj, I.A., Xia, G.: Tight lower bounds for certain parameterized NP-hard problems. Information and Computation\u00a0201(2), 216\u2013231 (2005)","journal-title":"Information and Computation"},{"issue":"4","key":"20_CR6","doi-asserted-by":"publisher","first-page":"1077","DOI":"10.1137\/050646354","volume":"37","author":"J. Chen","year":"2007","unstructured":"Chen, J., Fernau, H., Kanj, I.A., Xia, G.: Parametric duality and kernelization: lower bounds and upper bounds on kernel size. SIAM Journal on Computing\u00a037(4), 1077\u20131106 (2007)","journal-title":"SIAM Journal on Computing"},{"key":"20_CR7","doi-asserted-by":"crossref","unstructured":"Chen, J., Huang, X., Kanj, I.A., Xia, G.: Linear FPT reductions and computational lower bounds. In: STOC 2004, pp. 212\u2013221 (2004)","DOI":"10.1145\/1007352.1007391"},{"issue":"8","key":"20_CR8","doi-asserted-by":"publisher","first-page":"1346","DOI":"10.1016\/j.jcss.2006.04.007","volume":"72","author":"J. Chen","year":"2006","unstructured":"Chen, J., Huang, X., Kanj, I.A., Xia, G.: Strong Computational Lower Bounds via Parameterized Complexity. Journal of Computer and System Sceiences\u00a072(8), 1346\u20131367 (2006)","journal-title":"Journal of Computer and System Sceiences"},{"key":"20_CR9","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1006\/jagm.2001.1186","volume":"41","author":"J. Chen","year":"2001","unstructured":"Chen, J., Kanj, I.A., Jia, W.: Vertex cover: further observations and further improvements. Journal of Algorithms\u00a041, 280\u2013301 (2001)","journal-title":"Journal of Algorithms"},{"key":"20_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1007\/11821069_21","volume-title":"Mathematical Foundations of Computer Science 2006","author":"J. Chen","year":"2006","unstructured":"Chen, J., Kanj, I.A., Xia, G.: Improved Parameterized Upper Bounds for Vertex Cover. In: Kr\u00e1lovi\u010d, R., Urzyczyn, P. (eds.) MFCS 2006. LNCS, vol.\u00a04162, pp. 238\u2013249. Springer, Heidelberg (2006)"},{"key":"20_CR11","volume-title":"Graph Theory","author":"R. Diestel","year":"1996","unstructured":"Diestel, R.: Graph Theory. Springer, New York (1996)"},{"key":"20_CR12","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)"},{"key":"20_CR13","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Heidelberg (2006)"},{"issue":"2","key":"20_CR14","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1137\/S0097539702419649","volume":"36","author":"F. Fomin","year":"2006","unstructured":"Fomin, F., Thilikos, D.: Dominating sets in planar graphs: branch-width and exponential speed-up. SIAM Journal on Computing\u00a036(2), 281\u2013309 (2006)","journal-title":"SIAM Journal on Computing"},{"key":"20_CR15","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"M. Garey","year":"1979","unstructured":"Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, San Francisco (1979)"},{"key":"20_CR16","unstructured":"Johnson, D., Szegedy, M.: What are the least tractable instances of max independent set? In: SODA 1999, pp. 927\u2013928 (1999)"},{"key":"20_CR17","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.A., Perkovic, 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":"20_CR18","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1006\/jagm.1998.0996","volume":"31","author":"M. Mahajan","year":"1999","unstructured":"Mahajan, M., Raman, V.: Parameterizing above guaranteed values: Max-Sat and Max-Cut. Journal of Algorithms\u00a031, 335\u2013354 (1999)","journal-title":"Journal of Algorithms"},{"key":"20_CR19","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/BF01580444","volume":"8","author":"G.L. Nemhauser","year":"1975","unstructured":"Nemhauser, G.L., Trotter, L.E.: Vertex packing: structural properties and algorithms. Mathematical Programming\u00a08, 232\u2013248 (1975)","journal-title":"Mathematical Programming"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-02017-9_20.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,30]],"date-time":"2021-04-30T10:17:25Z","timestamp":1619777845000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-02017-9_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642020162","9783642020179"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-02017-9_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}