{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:01:39Z","timestamp":1725663699865},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540577850"},{"type":"electronic","value":"9783540483328"}],"license":[{"start":{"date-parts":[[1994,1,1]],"date-time":"1994-01-01T00:00:00Z","timestamp":757382400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-57785-8_167","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T13:20:48Z","timestamp":1330262448000},"page":"507-520","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On the structure of parameterized problems in NP"],"prefix":"10.1007","author":[{"given":"Liming","family":"Cai","sequence":"first","affiliation":[]},{"given":"Jianer","family":"Chen","sequence":"additional","affiliation":[]},{"given":"Rodney","family":"Downey","sequence":"additional","affiliation":[]},{"given":"Michael","family":"Fellows","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"unstructured":"K. Abrahamson, R. G. Downey and M. R. Fellows, Fixed-parameter intractability II, Lecture Notes in Computer Science (STACS'93), (1993), pp. 374\u2013385.","key":"41_CR1"},{"unstructured":"K. R. Abrahamson, J. A. Ellis, M. R. Fellows, and M. E. Mata, On the complexity of fixed parameter problems, Proc. 30th Annual Symposium on Foundations of Computer Science, (1989), pp. 210\u2013215.","key":"41_CR2"},{"key":"41_CR3","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1007\/3-540-19488-6_105","volume":"317","author":"S. Arnborg","year":"1988","unstructured":"S. Arnborg, J. Lagergren, and D. Seese, Problems easy for tree-decomposable graphs, Lecture Notes in Computer Science 317 (ICALP'88), (1988), pp. 38\u201351.","journal-title":"Lecture Notes in Computer Science"},{"unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy, Proof verification and intractability of approximation problems, Proc. 33rd Annual Symposium on Foundations of Computer Science, (1992), pp. 14\u201323.","key":"41_CR4"},{"doi-asserted-by":"crossref","unstructured":"J. Balcazar, J. Diaz, and J. Gabarro, Structural Complexity I, Springer-Verlag, 1988.","key":"41_CR5","DOI":"10.1007\/978-3-642-97062-7"},{"unstructured":"R. B. Boppana and M. Sipser, The complexity of finite functions, in Handbook of Theoretical Computer Science, Vol. A, J. van Leeuwen, ed., (1990), pp. 757\u2013804.","key":"41_CR6"},{"key":"41_CR7","doi-asserted-by":"crossref","first-page":"560","DOI":"10.1137\/0222038","volume":"22","author":"J. F. Buss","year":"1993","unstructured":"J. F. Buss and J. Goldsmith, Nondeterminism within P, SIAM J. Comput. 22, (1993), pp. 560\u2013572.","journal-title":"SIAM J. Comput."},{"unstructured":"S. Buss, Personal communication, (1992).","key":"41_CR8"},{"unstructured":"L. Cai and J. Chen, On input read-modes of alternating Turing machines, Technique Report 93\u2013046, Dept. Computer Science, Texas A&M University, (1993).","key":"41_CR9"},{"unstructured":"L. Cai and J. Chen, Fixed parameter tractability and approximability of NP- hard optimization problems, Proc. 2rd Israel Symposium on Theory of Computing and Systems, (1993), pp. 118\u2013126.","key":"41_CR10"},{"key":"41_CR11","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1007\/3-540-57182-5_23","volume":"711","author":"L. Cai","year":"1993","unstructured":"L. Cai and J. Chen, On the amount of nondeterminism and the power of verifying, Lecture Notes in Computer Science 711 (MFCS'93), (1993), pp. 311\u2013320.","journal-title":"Lecture Notes in Computer Science"},{"unstructured":"L. Cai, J. Chen, R. G. Downey, and M. R. Fellows, Advice classes of parameterized tractability, Proc. Asian Logic Conference, (1993).","key":"41_CR12"},{"key":"41_CR13","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/BF02090764","volume":"23","author":"J. Diaz","year":"1990","unstructured":"J. Diaz and J. Toran, Classes of bounded nondeterminism, Mathematical Systems Theory 23, (1990), pp. 21\u201332.","journal-title":"Mathematical Systems Theory"},{"unstructured":"R. G. Downey, P. A. Evans, and M. R. Fellows, Parameterized learning complexity, Proc. 6th ACM Workshop on Computational Learning Theory (COLT'93), (1993), pp. 51\u201357.","key":"41_CR14"},{"unstructured":"R. G. Downey and M. R. Fellows, Fixed-parameter intractability, Proc. 7th Structure in Complexity Theory Conference, (1992), pp. 36\u201349.","key":"41_CR15"},{"unstructured":"R. G. Downey and M. R. Fellows, Fixed parameter tractability and completeness, in Complexity Theory: Current Research, Ambos-Spies et al., ed., Cambridge University Press, (1993), pp. 191\u2013225.","key":"41_CR16"},{"doi-asserted-by":"crossref","unstructured":"M. R. Fellows, M. T. Hallett, and H. T. Wareham, DNA physical mapping: three ways of difficult, Proc. 1st European Symposium on Algorithms, (1993), 157\u2013168.","key":"41_CR17","DOI":"10.1007\/3-540-57273-2_52"},{"unstructured":"M. R. Fellows and M. A. Langston, On search, decision and the efficiency of polynomial-time algorithms, Proc. 21st ACM Symp. on Theory of Computing, (1989), pp. 501\u2013512.","key":"41_CR18"},{"doi-asserted-by":"crossref","unstructured":"M. R. Fellows and N. Koblitz, Fixed-parameter complexity and cryptography, Lecture Notes in Computer Science (AAECC10), (1993).","key":"41_CR19","DOI":"10.1007\/3-540-56686-4_38"},{"unstructured":"C. H. Papadimitriou and M. Yannakakis, On limited nondeterminism and the complexity of the V-C dimension, Proc. 8th Structure in Complexity Theory Conference, (1993), pp. 12\u201318.","key":"41_CR20"},{"key":"41_CR21","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1145\/322123.322138","volume":"26","author":"N. Pippenger","year":"1979","unstructured":"N. Pippenger and M. J. Fischer, Relations among complexity measures, J. Assoc. Comput. Mach. 26, (1979), pp. 361\u2013381.","journal-title":"J. Assoc. Comput. Mach."},{"unstructured":"J. Plehn and B. Voigt, Finding minimally weighted subgraphs, (1993), to appear.","key":"41_CR22"},{"unstructured":"N. Robertson and P. D. Seymour, Graph minors XV. Wagner's conjecture, to appear.","key":"41_CR23"},{"unstructured":"M. Sipser, Borel sets and circuit complexity, Proc. 15th Ann. ACM Symp. on Theory of Computing, (1983), pp. 61\u201369.","key":"41_CR24"},{"unstructured":"R. Szelepcsenyi, \u0392k-complete problems and greediness, Technique Report # 455, Computer Science Department, University of Rochester, (1993).","key":"41_CR25"},{"doi-asserted-by":"crossref","unstructured":"M. J. Wolf, Nondeterministic circuits, space complexity, and quasigroups, Theoretical Computer Science, to appear, 1993.","key":"41_CR26","DOI":"10.1016\/0304-3975(92)00014-I"}],"container-title":["Lecture Notes in Computer Science","STACS 94"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57785-8_167","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T23:28:22Z","timestamp":1578526102000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57785-8_167"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540577850","9783540483328"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/3-540-57785-8_167","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]},"assertion":[{"value":"31 May 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}