Improved kernel results for some 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
- 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
- (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
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1161563 (Why is no real title available?)
- 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 algorithmics for linear arrangement problems
- Parameterized Complexity for Domination Problems on Degenerate Graphs
- 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₂-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 kernelization complexity of connected domination in graphs with (no) small cycles
- The Parametrized Complexity of Some Fundamental Problems in Coding Theory
Cited in
(17)- An improved FPT algorithm for almost forest deletion problem
- On the parameterized complexity of contraction to generalization of trees
- An improved linear kernel for the cycle contraction problem
- An approximation algorithm for the \(l\)-pseudoforest deletion problem
- An improved linear kernel for complementary maximal strip recovery: simpler and smaller
- Improved PTAS for the constrained \(k\)-means problem
- Dealing with several parameterized problems by random methods
- Parameterized algorithms for edge biclique and related problems
- Faster deterministic algorithm for \textsc{Co-Path Set}
- Kernelization and randomized parameterized algorithms for co-path set problem
- Smaller kernels for several FPT problems based on simple observations
- On the parameterized complexity of contraction to generalization of trees
- Space-efficient graph kernelizations
- Revisiting path contraction and cycle contraction
- Revisiting path contraction and cycle contraction
- The complexity of contracting bipartite graphs into small cycles
- Graph modification of bounded size to minor-closed classes as fast as vertex deletion
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)
