{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T04:19:31Z","timestamp":1742617171777,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540565031"},{"type":"electronic","value":"9783540475743"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/3-540-56503-5_38","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T11:15:33Z","timestamp":1330254933000},"page":"374-385","source":"Crossref","is-referenced-by-count":6,"title":["Fixed-parameter intractability II (extended abstract)"],"prefix":"10.1007","author":[{"given":"Karl A.","family":"Abrahamson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rodney G.","family":"Downey","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael R.","family":"Fellows","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,27]]},"reference":[{"key":"38_CR1","unstructured":"K. Abrahamson, R. Downey, and M. Fellows, \u201cFixed Parameter Tractability and Completeness IV: W[P] and PSPACE,\u201d to appear."},{"key":"38_CR2","unstructured":"K. Ambos-Spies and A. Nies, \u201cThe Theory of The Polynomial Time Many-One Degrees is Undecidable,\u201d to appear."},{"key":"38_CR3","unstructured":"K. Ambos-Spies, A. Nies, and R.A. Shore, \u201cThe Theory of the Recursively Enumerable Weak Truth Table Degrees is Undecidable,\u201d to appear."},{"key":"38_CR4","unstructured":"K. Aoki, J. Shinoda, and T. Tsuda, \u201cOn \u03a02 Theories of hp-T Degrees of Low Sets,\u201d to appear."},{"key":"38_CR5","unstructured":"P. Cholak and R. Downey, \u201cUndecidability and Definability for Parameterized Polynomial Time Reducibilities,\u201d in preparation."},{"key":"38_CR6","unstructured":"R. Downey, \u201cNondiamond Theorems for Polymomial Time Reducibility,\u201d to appear, J.C.S.S."},{"key":"38_CR7","first-page":"161","volume":"87","author":"R. Downey","year":"1992","unstructured":"R. Downey and M. Fellows, \u201cFixed Parameter Tractability and Completeness,\u201d Congr. Num., 87 (1992) 161\u2013187.","journal-title":"Congr. Num."},{"key":"38_CR8","unstructured":"R. Downey and M. Fellows, \u201cFixed Parameter Tractability and Completeness I: Basic Results,\u201d to appear."},{"key":"38_CR9","unstructured":"R. Downey and M. Fellows, \u201cFixed Parameter Tractability and Completeness II: On Completeness for W[1],\u201d to appear."},{"key":"38_CR10","doi-asserted-by":"crossref","unstructured":"R. Downey and M. Fellows, \u201cFixed Parameter Intractability (Extended Abstract),\u201d Proc. 7th Conf. on Structure in Complexity Theory (1992), 36\u201349.","DOI":"10.1109\/SCT.1992.215379"},{"key":"38_CR11","unstructured":"R. Downey and M. Fellows, \u201cFixed Parameter Tractability and Completeness III: Some Structural Aspects of the W-Hierarchy,\u201d in preparation."},{"key":"38_CR12","unstructured":"R. Downey and M. Fellows, \u201cFixed Parameter Tractability,\u201d monograph in preparation."},{"key":"38_CR13","doi-asserted-by":"crossref","unstructured":"M. R. Fellows and M. A. Langston, \u201cOn Search, Decision and the Efficiency of Polynomial-Time Algorithms.\u201d In Proc. Symp. on Theory of Computing (STOC) (1989), 501\u2013512.","DOI":"10.1145\/73007.73055"},{"key":"38_CR14","doi-asserted-by":"crossref","unstructured":"M. R. Fellows and M. A. Langston, \u201cAn Analogue of the Myhill-Nerode Theorem and Its Use in Computing Finite Basis Characterizations.\u201d In Proc. Symp. Foundations of Comp. Sci. (FOCS) (1989), 520\u2013525.","DOI":"10.1109\/SFCS.1989.63528"},{"key":"38_CR15","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 (Freeman, San Francisco, 1979)."},{"key":"38_CR16","first-page":"155","volume":"22","author":"R. Ladner","year":"1975","unstructured":"R. Ladner, \u201cOn the Structure of Polynomial Time Reducibility,\u201d J.A.C.M. 22 (1975), 155\u2013171.","journal-title":"J.A.C.M."},{"key":"38_CR17","unstructured":"N. Robertson and P. D. Seymour, \u201cGraph Minors XIII. The Disjoint Paths Problem,\u201d to appear."},{"key":"38_CR18","unstructured":"N. Robertson and P. D. Seymour, \u201cGraph Minors XV. Wagner's Conjecture,\u201d to appear."},{"key":"38_CR19","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/0022-0000(78)90045-4","volume":"16","author":"T. J. Schaefer","year":"1978","unstructured":"T. J. Schaefer, \u201cComplexity of Some Two-person Perfect Information Games,\u201d J. Comput. Sys. Sci. 16 (1978), 185\u2013225.","journal-title":"J. Comput. Sys. Sci."},{"key":"38_CR20","unstructured":"J. Shinoda, Personal Communication, 1991."}],"container-title":["Lecture Notes in Computer Science","STACS 93"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-56503-5_38.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T21:49:36Z","timestamp":1742593776000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-56503-5_38"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540565031","9783540475743"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-56503-5_38","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1993]]}}}