The Lost Continent of Polynomial Time: Preprocessing and Kernelization

DOI10.1007/11847250_25MaRDI QIDQ3499745zbMATH OpenOpenAlexFDO

Authors Michael R. Fellows

Publication date 3 June 2008

Published in Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11847250_25

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) History of computer science (68-03) General topics in the theory of algorithms (68W01)

Recommendations

• Recent Developments in the Theory of Pre-processing
• Kernelization -- preprocessing with a guarantee
• Recent developments in kernelization: a survey
• Lower bounds on kernelization
• Lower bounds for kernelizations and other preprocessing procedures

Cited in

(21)

• A \(2k\) kernel for the cluster editing problem
• A more effective linear kernelization for cluster editing
• A complete parameterized complexity analysis of bounded planning
• Rotation distance is fixed-parameter tractable
• A simple and improved parameterized algorithm for bicluster editing
• A cubic-vertex kernel for flip consensus tree
• Cluster editing
• Search-space reduction via essential vertices
• Kernelization -- preprocessing with a guarantee
• Preprocessing to reduce the search space: antler structures for feedback vertex set
• Guarantees and limits of preprocessing in constraint satisfaction and reasoning
• Clustering with partial information
• What Is Known About Vertex Cover Kernelization?
• Meta-kernelization with structural parameters
• The parameterized complexity of the induced matching problem
• A linear kernel for the complementary maximal strip recovery problem
• Preprocessing to reduce the search space: antler structures for feedback vertex set
• Clustering with Partial Information
• Color spanning objects: algorithms and hardness results
• Parameterized Analysis of Art Gallery and Terrain Guarding
• An improved kernel size for rotation distance in binary trees

This page was built for publication: The Lost Continent of Polynomial Time: Preprocessing and Kernelization

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