Subexponential parameterized algorithms collapse the W-hierarchy

DOI10.1007/3-540-48224-5_23MaRDI QIDQ4535023zbMATH OpenFDO

Authors David W. Juedes, Liming Cai

Publication date 12 June 2002

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2076/20760273

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• On the existence of subexponential parameterized algorithms
• On Parameterized Exponential Time Complexity
• Tight lower bounds for certain parameterized NP-hard problems
• On parameterized exponential time complexity
• Subexponential Parameterized Algorithms

Cited in

(12)

• On the parameterized complexity of multiple-interval graph problems
• On problems without polynomial kernels
• On the existence of subexponential parameterized algorithms
• Algorithms in the W-hierarchy
• Tight lower bounds for certain parameterized NP-hard problems
• Parameterized complexity: the main ideas and connections to practical computing
• A basic parameterized complexity primer
• Confronting intractability via parameters
• On the parameterized complexity of compact set packing
• On the parameterized complexity of compact set packing
• Pathfinding in self-deleting graphs
• On miniaturized problems in parameterized complexity theory

Describes a project that uses

Uses Software

• c-sat

This page was built for publication: Subexponential parameterized algorithms collapse the W-hierarchy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4535023)