Improved kernel results for some 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
- Smaller kernels for several FPT problems based on simple observations
- Pseudo-kernelization: A branch-then-Reduce approach for FPT problems
- An improved kernel for the undirected planar feedback vertex set problem
- Improved kernels for several problems on planar graphs
- Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems
- Improved parameterized algorithms and kernels for mixed domination
- scientific article; zbMATH DE number 2080206
- FPT algorithms and kernels for the directed k-leaf problem
- An improved kernel for max-bisection above tight lower bound
- An improved linear kernel for the cycle contraction problem
Cites work
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1161563 (Why is no real title available?)
- (Meta) Kernelization
- A linear kernel for a planar connected dominating set
- A practical exact algorithm for the individual haplotyping problem MEC/GI
- Bidimensionality and kernels
- Chordal deletion is fixed-parameter tractable
- Cluster editing: kernelization based on edge cuts
- Color-coding
- Complexity and parameterized algorithms for cograph editing
- Connectivity is not a limit for kernelization: planar connected dominating set
- Contractibility and NP-completeness
- Crown structures for vertex cover kernelization
- Domination problems in nowhere-dense classes of graphs
- Edge-contraction problems
- Finding odd cycle transversals.
- Fixed-parameter complexity in AI and nonmonotonic reasoning
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Graph-modeled data clustering: Exact algorithms for clique generation
- Improved linear problem kernel for planar connected dominating set
- Improved parameterized algorithms for minimum link-length rectilinear spanning path problem
- Matching and weighted \(P_2\)-packing: algorithms and kernels
- Parameterized Complexity for Domination Problems on Degenerate Graphs
- Parameterized algorithmics for linear arrangement problems
- Parameterized complexity of control and bribery for \(d\)-approval elections
- Parameterized computational complexity of Dodgson and Young elections
- Planar graph vertex partition for linear problem kernels
- Radiation hybrid map construction problem parameterized
- Randomized parameterized algorithms for \(P_2\)-packing and co-path packing problems
- Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
- The Parametrized Complexity of Some Fundamental Problems in Coding Theory
- The kernelization complexity of connected domination in graphs with (no) small cycles
Cited in
(13)- An improved linear kernel for the cycle contraction problem
- On the parameterized complexity of contraction to generalization of trees
- Improved PTAS for the constrained \(k\)-means problem
- Dealing with several parameterized problems by random methods
- An improved linear kernel for complementary maximal strip recovery: simpler and smaller
- Parameterized algorithms for edge biclique and related problems
- Smaller kernels for several FPT problems based on simple observations
- Faster deterministic algorithm for \textsc{Co-Path Set}
- Space-efficient graph kernelizations
- Kernelization and randomized parameterized algorithms for co-path set problem
- On the parameterized complexity of contraction to generalization of trees
- An improved FPT algorithm for almost forest deletion problem
- An approximation algorithm for the \(l\)-pseudoforest deletion problem
This page was built for publication: Improved kernel results for some 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 Q507431)
