The Resource Parameterized complexity, R.G. Downey, M.R. Fellows, (electronic resource)

Parameterized complexity, R.G. Downey, M.R. Fellows, (electronic resource)

Label
Parameterized complexity
Title
Parameterized complexity
Statement of responsibility
R.G. Downey, M.R. Fellows
Creator
Contributor
Subject
Genre
Language
eng
Summary
This monograph presents an approach to complexity theory which offers a means of analysing algorithms in terms of their tractability. The authors consider the problem in terms of parameterized languages and taking "k-slices" of the language. In doing so, the reader is introduced to new classes of algorithms which may be analysed more precisely than hereto. The authors have made the book as self-contained as possible and a lot of background material is included. As a result, computer scientists, mathematicians, and graduate students interested in the design and analysis of algorithms will find much of interest in this book
Member of
Action
digitized
Cataloging source
OCLCE
http://library.link/vocab/creatorName
Downey, R. G.
Dewey number
511.3
Illustrations
illustrations
Index
index present
LC call number
QA267.7
LC item number
.D68 1999
Literary form
non fiction
Nature of contents
  • dictionaries
  • bibliography
http://library.link/vocab/relatedWorkOrContributorDate
1952-
http://library.link/vocab/relatedWorkOrContributorName
Fellows, M. R.
Series statement
Monographs in computer science
http://library.link/vocab/subjectName
  • Computational complexity
  • COMPUTABILIDADE E COMPLEXIDADE
  • Berechnungskomplexität
  • Computational complexity
Label
Parameterized complexity, R.G. Downey, M.R. Fellows, (electronic resource)
Link
http://dx.doi.org/10.1007/978-1-4612-0515-9
Instantiates
Publication
Antecedent source
file reproduced from original
Bibliography note
Includes bibliographical references (pages 489-516) and index
Carrier category
online resource
Carrier category code
cr
Carrier MARC source
rdacarrier
Color
black and white
Content category
text
Content type code
txt
Content type MARC source
rdacontent
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 Well-Quasi-Orderings and the Robertson-Seymour 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 k-Move Games -- 15 Provable Intractability: The Class XP -- III Structural and Other Results -- 16 Another Basis for the W -Hierarchy, the Tradeoff-Theorem, 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 W-Hierarchy 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
Extent
1 online resource (xv, 533 pages)
Form of item
online
Isbn
9781461267980
Isbn Type
(print)
Level of compression
  • lossless
  • lossy
Media category
computer
Media MARC source
rdamedia
Media type code
c
Other control number
10.1007/978-1-4612-0515-9
Other physical details
illustrations.
Reformatting quality
  • preservation
  • access
Reproduction note
Electronic reproduction.
Specific material designation
remote
System control number
  • (OCoLC)607099137
  • (OCoLC)ocn607099137
System details
Master and use copy. Digital master created according to Benchmark for Faithful Digital Reproductions of Monographs and Serials, Version 1. Digital Library Federation, December 2002.
Label
Parameterized complexity, R.G. Downey, M.R. Fellows, (electronic resource)
Link
http://dx.doi.org/10.1007/978-1-4612-0515-9
Publication
Antecedent source
file reproduced from original
Bibliography note
Includes bibliographical references (pages 489-516) and index
Carrier category
online resource
Carrier category code
cr
Carrier MARC source
rdacarrier
Color
black and white
Content category
text
Content type code
txt
Content type MARC source
rdacontent
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 Well-Quasi-Orderings and the Robertson-Seymour 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 k-Move Games -- 15 Provable Intractability: The Class XP -- III Structural and Other Results -- 16 Another Basis for the W -Hierarchy, the Tradeoff-Theorem, 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 W-Hierarchy 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
Extent
1 online resource (xv, 533 pages)
Form of item
online
Isbn
9781461267980
Isbn Type
(print)
Level of compression
  • lossless
  • lossy
Media category
computer
Media MARC source
rdamedia
Media type code
c
Other control number
10.1007/978-1-4612-0515-9
Other physical details
illustrations.
Reformatting quality
  • preservation
  • access
Reproduction note
Electronic reproduction.
Specific material designation
remote
System control number
  • (OCoLC)607099137
  • (OCoLC)ocn607099137
System details
Master and use copy. Digital master created according to Benchmark for Faithful Digital Reproductions of Monographs and Serials, Version 1. Digital Library Federation, December 2002.

Library Locations

  • Architecture LibraryBorrow it
    Gould Hall 830 Van Vleet Oval Rm. 105, Norman, OK, 73019, US
    35.205706 -97.445050
  • Bizzell Memorial LibraryBorrow it
    401 W. Brooks St., Norman, OK, 73019, US
    35.207487 -97.447906
  • Boorstin CollectionBorrow it
    401 W. Brooks St., Norman, OK, 73019, US
    35.207487 -97.447906
  • Chinese Literature Translation ArchiveBorrow it
    401 W. Brooks St., RM 414, Norman, OK, 73019, US
    35.207487 -97.447906
  • Engineering LibraryBorrow it
    Felgar Hall 865 Asp Avenue, Rm. 222, Norman, OK, 73019, US
    35.205706 -97.445050
  • Fine Arts LibraryBorrow it
    Catlett Music Center 500 West Boyd Street, Rm. 20, Norman, OK, 73019, US
    35.210371 -97.448244
  • Harry W. Bass Business History CollectionBorrow it
    401 W. Brooks St., Rm. 521NW, Norman, OK, 73019, US
    35.207487 -97.447906
  • History of Science CollectionsBorrow it
    401 W. Brooks St., Rm. 521NW, Norman, OK, 73019, US
    35.207487 -97.447906
  • John and Mary Nichols Rare Books and Special CollectionsBorrow it
    401 W. Brooks St., Rm. 509NW, Norman, OK, 73019, US
    35.207487 -97.447906
  • Library Service CenterBorrow it
    2601 Technology Place, Norman, OK, 73019, US
    35.185561 -97.398361
  • Price College Digital LibraryBorrow it
    Adams Hall 102 307 West Brooks St., Norman, OK, 73019, US
    35.210371 -97.448244
  • Western History CollectionsBorrow it
    Monnet Hall 630 Parrington Oval, Rm. 300, Norman, OK, 73019, US
    35.209584 -97.445414
Processing Feedback ...