Kernelization techniques and its applications to parameterized computation

DOI10.3724/SP.J.1001.2009.03593MaRDI QIDQ3054241zbMATH OpenFDO

Authors Jianxin Wang, Qilong Feng, Shao-Hua Li, Jianer Chen

Publication date 5 November 2010

Published in Journal of Software (Search for Journal in Brave)

Full work available at URL https://doi.org/10.3724/SP.J.1001.2009.03593

zbMATH Keywords

randomized algorithmkernelizationcrown decompositionextremal induction

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Recommendations

• Kernelization -- preprocessing with a guarantee
• Kernelization: new upper and lower bound techniques
• Smaller kernels for several FPT problems based on simple observations
• Lower bounds for kernelization
• Towards a Taxonomy of Techniques for Designing Parameterized Algorithms

Cited in

(8)

• Kernelization Lower Bounds by Cross-Composition
• Smaller kernels for several FPT problems based on simple observations
• An Efficient Algorithm for Computing Kernel Function Defined with Anti-unification
• Pseudo-kernelization: A branch-then-Reduce approach for FPT problems
• Extremal kernelization: a commemorative paper
• STACS 2005
• Towards a Taxonomy of Techniques for Designing Parameterized Algorithms
• scientific article; zbMATH DE number 6781341 (Why is no real title available?)

This page was built for publication: Kernelization techniques and its applications to parameterized computation

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