{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:26:56Z","timestamp":1761611216526},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540422877"},{"type":"electronic","value":"9783540482246"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-48224-5_23","type":"book-chapter","created":{"date-parts":[[2007,10,28]],"date-time":"2007-10-28T06:29:04Z","timestamp":1193552944000},"page":"273-284","source":"Crossref","is-referenced-by-count":18,"title":["Subexponential Parameterized Algorithms Collapse the W-Hierarchy"],"prefix":"10.1007","author":[{"given":"Liming","family":"Cai","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Juedes","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,7,4]]},"reference":[{"key":"23_CR1","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/3-540-44985-X_10","volume-title":"Proceedings of the 7th Scandinavian Workshop on Algorithm Theory (SWAT 2000)","author":"J. Alber","year":"2000","unstructured":"J. Alber, H. Bodlaender, H. Fernau, and R. Niedermeier. Fixed parameter algorithms for planar dominating set and related problems. In Proceedings of the 7th Scandinavian Workshop on Algorithm Theory (SWAT 2000), volume 1851 of Lecture Notes in Computer Science, pages 97\u2013110. Springer-Verlag, 2000."},{"key":"23_CR2","doi-asserted-by":"crossref","unstructured":"J. Alber, J. Gramm, and R. Niedermeier. Faster exact algorithms for hard problems: A parameterized point of view. Discrete Mathematics, 2001. to appear.","DOI":"10.1016\/S0012-365X(00)00199-0"},{"key":"23_CR3","unstructured":"S. Arora and C. Lund. Hardness of approximations. In Dorit Hochbaum, editor, Approximation Algorithms for NP-hard problems, pages 399\u2013446. PWS Publishing, 1997."},{"key":"23_CR4","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"B. S. Baker","year":"1994","unstructured":"B. S. Baker. Approximation algorithms for NP-complete problems on planar graphs. Journal of the ACM, 41:153\u2013180, 1994.","journal-title":"Journal of the ACM"},{"key":"23_CR5","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/S0020-0190(97)00213-5","volume":"65","author":"R. Balasubramanian","year":"1998","unstructured":"R. Balasubramanian, M. R. Fellows, and V. Raman. An improved fixed parameter algorithm for vertex cover. Information Processing Letters, 65:163\u2013168, 1998.","journal-title":"Information Processing Letters"},{"issue":"1","key":"23_CR6","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1137\/S0097539792228289","volume":"23","author":"M. Bellare","year":"1994","unstructured":"M. Bellare and S. Goldwasser. The complexity of decision versus search. SIAM Journal on Computing, 23(1):97\u2013119, February 1994.","journal-title":"SIAM Journal on Computing"},{"key":"23_CR7","unstructured":"S. Buss, 1989. Personal Communication with Downey and Fellows cited in [12, p.5]."},{"issue":"3","key":"23_CR8","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1006\/jcss.1997.1490","volume":"54","author":"L. Cai","year":"1997","unstructured":"L. Cai and J. Chen. On fixed-parameter tractability and approximability of NP optimization problems. Journal of Computer and System Sciences, 54(3):465\u2013474, June 1997.","journal-title":"Journal of Computer and System Sciences"},{"key":"23_CR9","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1007\/3-540-46784-X_30","volume-title":"Proceedings of the 25th International Workshop on Graph-Theoretical Concepts in Computer Science","author":"J. Chen","year":"1999","unstructured":"J. Chen, I. A. Kanj, and W. Jia. Vertex cover: Further observations and further improvements. In Proceedings of the 25th International Workshop on Graph-Theoretical Concepts in Computer Science, volume 1665 of Lecture Notes in Computer Science, pages 313\u2013324. Springer-Verlag, 1999."},{"key":"23_CR10","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0304-3975(94)00097-3","volume":"141","author":"R. G. Downey","year":"1995","unstructured":"R. G. Downey and M. R. Fellows. Fixed-parameter tractability and completeness II: On completeness for W[1]. Theoretical Computer Science, 141:109\u2013131, 1995.","journal-title":"Theoretical Computer Science"},{"key":"23_CR11","doi-asserted-by":"crossref","unstructured":"R. G. Downey and M. R. Fellows. Parameterized computational feasibility. In Proceedings of Feasible Mathematics II, pages 219\u2013244. Birkhauser, 1995.","DOI":"10.1007\/978-1-4612-2566-9_7"},{"key":"23_CR12","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R. G. Downey","year":"1999","unstructured":"R. G. Downey and M. R. Fellows. Parameterized Complexity. Springer-Verlag, New York, 1999."},{"key":"23_CR13","unstructured":"R. G. Downey, M. R. Fellows, and U. Stege. Parameterized complexity: A framework for systematically confronting computational intractability. In Contemporary Trends in Discrete Mathematics: From DIMACS to DIMATIA to the Future, volume 49 of AMS-DIMACS Proceeding Series, pages 49\u201399. AMS, 1999."},{"key":"23_CR14","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-completeness. W.H. Freeman and Company, San Francisco, 1979."},{"key":"23_CR15","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo, R. Paturi, and F. Zane. Which problems have strongly exponential complexity? In Proceedings of the 39th Symposium on Foundations of Computer Science, pages 653\u2013664. IEEE Computer Society Press, 1998.","DOI":"10.1109\/SFCS.1998.743516"},{"key":"23_CR16","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1006\/jagm.1998.0996","volume":"31","author":"M. Mahajan","year":"1999","unstructured":"M. Mahajan and V. Raman. Parameterizing above guaranteed values:MaxSat and MaxCut. Journal of Algorithms, 31:335\u2013354, 1999.","journal-title":"Journal of Algorithms"},{"key":"23_CR17","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"561","DOI":"10.1007\/3-540-49116-3_53","volume-title":"Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science","author":"R. Niedermeier","year":"1999","unstructured":"R. Niedermeier and P. Rossmanith. Upper bounds for vertex cover further improved. In Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science, volume 1563 of Lecture Notes in Computer Science, pages 561\u2013570. Springer-Verlag, 1999."},{"key":"23_CR18","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C. H. Papadimitriou","year":"1991","unstructured":"C. H. Papadimitriou and M. Yannakakis. Optimization, approximation, and complexity classes. Journal of Computer and Systems Sciences, 43:425\u2013440, 1991.","journal-title":"Journal of Computer and Systems Sciences"}],"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-48224-5_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,24]],"date-time":"2019-02-24T19:29:48Z","timestamp":1551036588000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48224-5_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540422877","9783540482246"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/3-540-48224-5_23","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}