The Lost Continent of Polynomial Time: Preprocessing and Kernelization
From MaRDI portal
Publication:3499745
DOI10.1007/11847250_25zbMATH Open1154.68560OpenAlexW1531772464MaRDI QIDQ3499745FDOQ3499745
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
Recommendations
Analysis of algorithms and problem complexity (68Q25) History of computer science (68-03) General topics in the theory of algorithms (68W01)
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
- What Is Known About Vertex Cover Kernelization?
- Clustering with partial information
- 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
- Parameterized Analysis of Art Gallery and Terrain Guarding
- Color spanning objects: algorithms and hardness results
- 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)
