On parameterized intractability: Hardness and completeness Academic Article

abstract

• We study the theory and techniques developed in the research of parameterized intractability, emphasizing on parameterized hardness and completeness that imply (stronger) computational lower bounds for natural computational problems. Moreover, the fundamentals of the structural properties in parameterized complexity theory, relationships to classical complexity theory and more recent developments in the area are also introduced. The Author 2008. Published by Oxford University Press on behalf of The British Computer Society. All rights reserved.

authors

• Chen, Jianer

published proceedings

• COMPUTER JOURNAL

author list (cited authors)

• Chen, J., & Meng, J.

citation count

• 11

complete list of authors

• Chen, Jianer||Meng, Jie

publication date

• January 2008

publisher

• Oxford University Press (OUP)  Publisher

published in

• The Computer Journal  Journal

keywords

• Exact Algorithm
• Fixed Parameter Tractability
• Parameterized Computation
• W-hierarchy

Digital Object Identifier (DOI)

• 10.1093/comjnl/bxm036

start page

• 39

end page

• 59

volume

• 51

issue

• 1

URL

• http%3A%2F%2Fdx.doi.org%2F10.1093%2Fcomjnl%2Fbxm036