Smaller kernels for several FPT problems based on simple observations
From MaRDI portal
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
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
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- 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
- Obtaining a bipartite graph by contracting few edges
- Parameterized Complexity for Domination Problems on Degenerate Graphs
- Parameterized algorithmics for linear arrangement problems
- 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)
