The Lost Continent of Polynomial Time: Preprocessing and Kernelization

DOI10.1007/11847250_25zbMath1154.68560OpenAlexW1531772464MaRDI QIDQ3499745

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)

Related Items (19)

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

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