Smaller kernels for several FPT problems based on simple observations
From MaRDI portal
Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)
Recommendations
- Improved kernel results for some FPT problems based on simple observations
- Lower bounds on kernelization
- Kernels: Annotated, Proper and Induced
- Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
- Kernelization techniques and its applications to parameterized computation
Cites work
- A linear kernel for a planar connected dominating set
- An improved kernel for planar connected dominating set
- Bidimensionality and kernels
- Chordal Deletion Is Fixed-Parameter Tractable
- Connectivity is not a limit for kernelization: planar connected dominating set
- Domination problems in nowhere-dense classes of graphs
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- Obtaining a bipartite graph by contracting few edges
- Parameterized algorithmics for linear arrangement problems
- Parameterized Complexity for Domination Problems on Degenerate Graphs
- Radiation hybrid map construction problem parameterized
- Randomized parameterized algorithms for co-path set problem
- Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
- The kernelization complexity of connected domination in graphs with (no) small cycles
Cited in
(2)
This page was built for publication: Smaller kernels for several FPT problems based on simple observations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3452562)
