Kernels: Annotated, Proper and Induced

DOI10.1007/11847250_24MaRDI QIDQ3499744zbMATH OpenOpenAlexFDO

Authors Faisal N. Abu-Khzam, Henning Fernau

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_24

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) General topics in the theory of algorithms (68W01)

Recommendations

• On problems without polynomial kernels
• Lower bounds on kernelization
• On Problems without Polynomial Kernels (Extended Abstract)
• Kernelization: new upper and lower bound techniques
• Lower bounds for kernelization

Cited in

(20)

• A new bound for 3-satisfiable MaxSat and its algorithmic application
• A fast branching algorithm for cluster vertex deletion
• A new bound for 3-satisfiable MaxSat and its algorithmic application
• Parameterized mixed graph coloring
• A top-down approach to search-trees: Improved algorithmics for 3-hitting set
• Smaller kernels for several FPT problems based on simple observations
• A kernelization algorithm for \(d\)-hitting set
• Fixed-parameter algorithms for cluster vertex deletion
• Approximability of clique transversal in perfect graphs
• Editing graphs to satisfy degree constraints: a parameterized approach
• A cubic-vertex kernel for flip consensus tree
• Extremal kernelization: a commemorative paper
• Breaking the \(2^{n}\)-barrier for irredundance: two lines of attack
• Fixed-Parameter Algorithms for Cluster Vertex Deletion
• Meta-kernelization with structural parameters
• Parameterized complexity of \(k\)-Chinese postman problem
• Vertex and edge covers with clustering properties: Complexity and algorithms
• Fixed parameter algorithms for one-sided crossing minimization revisited
• Editing graphs into few cliques: complexity, approximation, and kernelization schemes
• Fixed-parameter tractability results for feedback set problems in tournaments

This page was built for publication: Kernels: Annotated, Proper and Induced

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