Borrow it
 Architecture Library
 Bizzell Memorial Library
 Boorstin Collection
 Chinese Literature Translation Archive
 Engineering Library
 Fine Arts Library
 Harry W. Bass Business History Collection
 History of Science Collections
 John and Mary Nichols Rare Books and Special Collections
 Library Service Center
 Price College Digital Library
 Western History Collections
The Resource Parameterized Complexity, by Rodney G. Downey, M.R. Fellows, (electronic resource)
Parameterized Complexity, by Rodney G. Downey, M.R. Fellows, (electronic resource)
Resource Information
The item Parameterized Complexity, by Rodney G. Downey, M.R. Fellows, (electronic resource) represents a specific, individual, material embodiment of a distinct intellectual or artistic creation found in University of Oklahoma Libraries.This item is available to borrow from all library branches.
Resource Information
The item Parameterized Complexity, by Rodney G. Downey, M.R. Fellows, (electronic resource) represents a specific, individual, material embodiment of a distinct intellectual or artistic creation found in University of Oklahoma Libraries.
This item is available to borrow from all library branches.
 Summary
 The idea for this book was conceived over the second bottle of Villa Maria's Caber net Medot '89, at the dinner of the Australasian Combinatorics Conference held at Palmerston North, New Zealand in December 1990, where the authors first met and discovered they had a number of interests in common. Initially, we embarked on a small project to try to formulate reductions to address the apparent parame terized intractability of DOMINATING SET, and to introduce a structure in which to frame our answers. Having spent several months trying to get the definitions for the reductions right (they now seem so obvious), we turned to our tattered copies of Garey and Johnson's work [239]. We were stunned to find that virtually none of the classical reductions worked in the parameterized setting. We then wondered if we'd be able to find any interesting reductions. Several years, many more bottles, so many papers, and reductions later it [3] seemed that we had unwittingly stumbled upon what we believe is a truly central and new area of complexity theory. It seemed to us that the material would be of great interest to people working in areas where exact algorithms for a small range of parameters are natural and useful (e. g. , Molecular Biology, VLSI design). The tractability theory was rich with distinctive and powerful techniques. The intractability theory seemed to have a deep structure and techniques all of its own
 Language

 eng
 eng
 Edition
 1st ed. 1999.
 Extent
 1 online resource (XV, 533 p.)
 Note
 "With 68 figures."
 Contents

 1 Computers, Complexity, and Intractability from the Parametric Point of View
 1.1 Introduction
 1.2 The Role of Computational Complexity in Modern Science
 1.3 The Story of Dr.O, Continued
 1.4 Reworking the Foundations of Computational Complexity
 1.5 A Deal with the Devil
 1.6 How Parameters Arise in Practice
 1.7 A Distinctive Positive Toolkit
 1.8 O No?
 1.9 The Barometer of Parametric Intractability
 1.10 Structural Aspects of Parameterized Complexity
 1.11 An Overview of Current Research Horizons
 I Parameterized Tractability
 2 The Basic Definitions
 3 Some Ad Hoc Methods: The Methods of Bounded Search Tree and Problem Kernel
 4 Optimization Problems, Approximation Schemes, and Their Relation with FPT
 5 The Advice View Revisited and LOGSPACE
 6 Methods via Automata and Bounded Treewidth
 7 WellQuasiOrderings and the RobertsonSeymour Theorems
 8 Miscellaneous Techniques
 II Parameterized Intractability
 9 Reductions
 10 The Basic Class W[1] and an Analog of Cook’s Theorem
 11 Some Other W[1]Hardness Results
 12 The W Hierarchy
 13 Beyond W[t]Hardness
 14 Fixed Parameter Analogs of PSPACE and kMove Games
 15 Provable Intractability: The Class XP
 III Structural and Other Results
 16 Another Basis for the W Hierarchy, the TradeoffTheorem, and Randomized Reductions
 17 Relationships with Classical Complexity and Limited Nondeterminism
 18 The Monotone and Antimonotone Collapse Theorems: MONOTONEW[2t + 1] = W[2t] and ANTIMONOTONEW[2t + 2] = W[2t + 1]
 19 The Structure of Languages Under Parameterized Reducibilities
 IV Appendix
 A A Problem Compendium and Guide to WHierarchy Completeness, Hardness, and Classification; and Some Research Horizons
 B Research Horizons
 B.2 A Lineup of Tough Customers
 B.3 Connections Between Classical and Parameterized Complexity
 B.4 Classification Gaps
 B.5 Structural Issues and Analogs of Classical Results
 References
 Isbn
 9781461205159
 Label
 Parameterized Complexity
 Title
 Parameterized Complexity
 Statement of responsibility
 by Rodney G. Downey, M.R. Fellows
 Language

 eng
 eng
 Summary
 The idea for this book was conceived over the second bottle of Villa Maria's Caber net Medot '89, at the dinner of the Australasian Combinatorics Conference held at Palmerston North, New Zealand in December 1990, where the authors first met and discovered they had a number of interests in common. Initially, we embarked on a small project to try to formulate reductions to address the apparent parame terized intractability of DOMINATING SET, and to introduce a structure in which to frame our answers. Having spent several months trying to get the definitions for the reductions right (they now seem so obvious), we turned to our tattered copies of Garey and Johnson's work [239]. We were stunned to find that virtually none of the classical reductions worked in the parameterized setting. We then wondered if we'd be able to find any interesting reductions. Several years, many more bottles, so many papers, and reductions later it [3] seemed that we had unwittingly stumbled upon what we believe is a truly central and new area of complexity theory. It seemed to us that the material would be of great interest to people working in areas where exact algorithms for a small range of parameters are natural and useful (e. g. , Molecular Biology, VLSI design). The tractability theory was rich with distinctive and powerful techniques. The intractability theory seemed to have a deep structure and techniques all of its own
 http://library.link/vocab/creatorName
 Downey, Rodney G
 Dewey number
 004.0151
 http://bibfra.me/vocab/relation/httpidlocgovvocabularyrelatorsaut

 f1vwziqzBNo
 He9XHCrpEmE
 Image bit depth
 0
 Language note
 English
 LC call number
 QA75.576.95
 Literary form
 non fiction
 Nature of contents
 dictionaries
 http://library.link/vocab/relatedWorkOrContributorName
 Fellows, M.R.
 Series statement
 Monographs in Computer Science,
 http://library.link/vocab/subjectName

 Information theory
 Logic, Symbolic and mathematical
 Mathematics
 Combinatorics
 Computer software
 Theory of Computation
 Mathematical Logic and Foundations
 Applications of Mathematics
 Combinatorics
 Algorithm Analysis and Problem Complexity
 Label
 Parameterized Complexity, by Rodney G. Downey, M.R. Fellows, (electronic resource)
 Note
 "With 68 figures."
 Antecedent source
 mixed
 Bibliography note
 Includes bibliographical references and index
 Carrier category
 online resource
 Carrier category code

 cr
 Color
 not applicable
 Content category
 text
 Content type code

 txt
 Contents
 1 Computers, Complexity, and Intractability from the Parametric Point of View  1.1 Introduction  1.2 The Role of Computational Complexity in Modern Science  1.3 The Story of Dr.O, Continued  1.4 Reworking the Foundations of Computational Complexity  1.5 A Deal with the Devil  1.6 How Parameters Arise in Practice  1.7 A Distinctive Positive Toolkit  1.8 O No?  1.9 The Barometer of Parametric Intractability  1.10 Structural Aspects of Parameterized Complexity  1.11 An Overview of Current Research Horizons  I Parameterized Tractability  2 The Basic Definitions  3 Some Ad Hoc Methods: The Methods of Bounded Search Tree and Problem Kernel  4 Optimization Problems, Approximation Schemes, and Their Relation with FPT  5 The Advice View Revisited and LOGSPACE  6 Methods via Automata and Bounded Treewidth  7 WellQuasiOrderings and the RobertsonSeymour Theorems  8 Miscellaneous Techniques  II Parameterized Intractability  9 Reductions  10 The Basic Class W[1] and an Analog of Cook’s Theorem  11 Some Other W[1]Hardness Results  12 The W Hierarchy  13 Beyond W[t]Hardness  14 Fixed Parameter Analogs of PSPACE and kMove Games  15 Provable Intractability: The Class XP  III Structural and Other Results  16 Another Basis for the W Hierarchy, the TradeoffTheorem, and Randomized Reductions  17 Relationships with Classical Complexity and Limited Nondeterminism  18 The Monotone and Antimonotone Collapse Theorems: MONOTONEW[2t + 1] = W[2t] and ANTIMONOTONEW[2t + 2] = W[2t + 1]  19 The Structure of Languages Under Parameterized Reducibilities  IV Appendix  A A Problem Compendium and Guide to WHierarchy Completeness, Hardness, and Classification; and Some Research Horizons  B Research Horizons  B.2 A Lineup of Tough Customers  B.3 Connections Between Classical and Parameterized Complexity  B.4 Classification Gaps  B.5 Structural Issues and Analogs of Classical Results  References
 Dimensions
 unknown
 Edition
 1st ed. 1999.
 Extent
 1 online resource (XV, 533 p.)
 File format
 multiple file formats
 Form of item
 online
 Isbn
 9781461205159
 Level of compression
 uncompressed
 Media category
 computer
 Media type code

 c
 Other control number
 10.1007/9781461205159
 Quality assurance targets
 absent
 Reformatting quality
 access
 Specific material designation
 remote
 System control number

 (CKB)3400000000089163
 (SSID)ssj0000934735
 (PQKBManifestationID)11520545
 (PQKBTitleCode)TC0000934735
 (PQKBWorkID)10931169
 (PQKB)10569223
 (DEHe213)9781461205159
 (MiAaPQ)EBC3074976
 (EXLCZ)993400000000089163
 Label
 Parameterized Complexity, by Rodney G. Downey, M.R. Fellows, (electronic resource)
 Note
 "With 68 figures."
 Antecedent source
 mixed
 Bibliography note
 Includes bibliographical references and index
 Carrier category
 online resource
 Carrier category code

 cr
 Color
 not applicable
 Content category
 text
 Content type code

 txt
 Contents
 1 Computers, Complexity, and Intractability from the Parametric Point of View  1.1 Introduction  1.2 The Role of Computational Complexity in Modern Science  1.3 The Story of Dr.O, Continued  1.4 Reworking the Foundations of Computational Complexity  1.5 A Deal with the Devil  1.6 How Parameters Arise in Practice  1.7 A Distinctive Positive Toolkit  1.8 O No?  1.9 The Barometer of Parametric Intractability  1.10 Structural Aspects of Parameterized Complexity  1.11 An Overview of Current Research Horizons  I Parameterized Tractability  2 The Basic Definitions  3 Some Ad Hoc Methods: The Methods of Bounded Search Tree and Problem Kernel  4 Optimization Problems, Approximation Schemes, and Their Relation with FPT  5 The Advice View Revisited and LOGSPACE  6 Methods via Automata and Bounded Treewidth  7 WellQuasiOrderings and the RobertsonSeymour Theorems  8 Miscellaneous Techniques  II Parameterized Intractability  9 Reductions  10 The Basic Class W[1] and an Analog of Cook’s Theorem  11 Some Other W[1]Hardness Results  12 The W Hierarchy  13 Beyond W[t]Hardness  14 Fixed Parameter Analogs of PSPACE and kMove Games  15 Provable Intractability: The Class XP  III Structural and Other Results  16 Another Basis for the W Hierarchy, the TradeoffTheorem, and Randomized Reductions  17 Relationships with Classical Complexity and Limited Nondeterminism  18 The Monotone and Antimonotone Collapse Theorems: MONOTONEW[2t + 1] = W[2t] and ANTIMONOTONEW[2t + 2] = W[2t + 1]  19 The Structure of Languages Under Parameterized Reducibilities  IV Appendix  A A Problem Compendium and Guide to WHierarchy Completeness, Hardness, and Classification; and Some Research Horizons  B Research Horizons  B.2 A Lineup of Tough Customers  B.3 Connections Between Classical and Parameterized Complexity  B.4 Classification Gaps  B.5 Structural Issues and Analogs of Classical Results  References
 Dimensions
 unknown
 Edition
 1st ed. 1999.
 Extent
 1 online resource (XV, 533 p.)
 File format
 multiple file formats
 Form of item
 online
 Isbn
 9781461205159
 Level of compression
 uncompressed
 Media category
 computer
 Media type code

 c
 Other control number
 10.1007/9781461205159
 Quality assurance targets
 absent
 Reformatting quality
 access
 Specific material designation
 remote
 System control number

 (CKB)3400000000089163
 (SSID)ssj0000934735
 (PQKBManifestationID)11520545
 (PQKBTitleCode)TC0000934735
 (PQKBWorkID)10931169
 (PQKB)10569223
 (DEHe213)9781461205159
 (MiAaPQ)EBC3074976
 (EXLCZ)993400000000089163
Library Locations

Architecture LibraryBorrow itGould Hall 830 Van Vleet Oval Rm. 105, Norman, OK, 73019, US35.205706 97.445050



Chinese Literature Translation ArchiveBorrow it401 W. Brooks St., RM 414, Norman, OK, 73019, US35.207487 97.447906

Engineering LibraryBorrow itFelgar Hall 865 Asp Avenue, Rm. 222, Norman, OK, 73019, US35.205706 97.445050

Fine Arts LibraryBorrow itCatlett Music Center 500 West Boyd Street, Rm. 20, Norman, OK, 73019, US35.210371 97.448244

Harry W. Bass Business History CollectionBorrow it401 W. Brooks St., Rm. 521NW, Norman, OK, 73019, US35.207487 97.447906

History of Science CollectionsBorrow it401 W. Brooks St., Rm. 521NW, Norman, OK, 73019, US35.207487 97.447906

John and Mary Nichols Rare Books and Special CollectionsBorrow it401 W. Brooks St., Rm. 509NW, Norman, OK, 73019, US35.207487 97.447906


Price College Digital LibraryBorrow itAdams Hall 102 307 West Brooks St., Norman, OK, 73019, US35.210371 97.448244

Western History CollectionsBorrow itMonnet Hall 630 Parrington Oval, Rm. 300, Norman, OK, 73019, US35.209584 97.445414
Embed
Settings
Select options that apply then copy and paste the RDF/HTML data fragment to include in your application
Embed this data in a secure (HTTPS) page:
Layout options:
Include data citation:
<div class="citation" vocab="http://schema.org/"><i class="fa faexternallinksquare fafw"></i> Data from <span resource="http://link.libraries.ou.edu/portal/ParameterizedComplexitybyRodneyG.Downey/7iBG5ql6nu0/" typeof="Book http://bibfra.me/vocab/lite/Item"><span property="name http://bibfra.me/vocab/lite/label"><a href="http://link.libraries.ou.edu/portal/ParameterizedComplexitybyRodneyG.Downey/7iBG5ql6nu0/">Parameterized Complexity, by Rodney G. Downey, M.R. Fellows, (electronic resource)</a></span>  <span property="potentialAction" typeOf="OrganizeAction"><span property="agent" typeof="LibrarySystem http://library.link/vocab/LibrarySystem" resource="http://link.libraries.ou.edu/"><span property="name http://bibfra.me/vocab/lite/label"><a property="url" href="http://link.libraries.ou.edu/">University of Oklahoma Libraries</a></span></span></span></span></div>
Note: Adjust the width and height settings defined in the RDF/HTML code fragment to best match your requirements
Preview
Cite Data  Experimental
Data Citation of the Item Parameterized Complexity, by Rodney G. Downey, M.R. Fellows, (electronic resource)
Copy and paste the following RDF/HTML data fragment to cite this resource
<div class="citation" vocab="http://schema.org/"><i class="fa faexternallinksquare fafw"></i> Data from <span resource="http://link.libraries.ou.edu/portal/ParameterizedComplexitybyRodneyG.Downey/7iBG5ql6nu0/" typeof="Book http://bibfra.me/vocab/lite/Item"><span property="name http://bibfra.me/vocab/lite/label"><a href="http://link.libraries.ou.edu/portal/ParameterizedComplexitybyRodneyG.Downey/7iBG5ql6nu0/">Parameterized Complexity, by Rodney G. Downey, M.R. Fellows, (electronic resource)</a></span>  <span property="potentialAction" typeOf="OrganizeAction"><span property="agent" typeof="LibrarySystem http://library.link/vocab/LibrarySystem" resource="http://link.libraries.ou.edu/"><span property="name http://bibfra.me/vocab/lite/label"><a property="url" href="http://link.libraries.ou.edu/">University of Oklahoma Libraries</a></span></span></span></span></div>