Improved kernel results for some FPT problems based on simple observations
DOI10.1016/J.TCS.2016.06.012zbMATH Open1356.68102OpenAlexW2425261484MaRDI QIDQ507431FDOQ507431
Authors: Wen-Jun Li, Qilong Feng, Shuai Hu, Jianer Chen 
Publication date: 6 February 2017
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2016.06.012
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
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)
Cites Work
- Title not available (Why is that?)
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Finding odd cycle transversals.
- Color-coding
- Title not available (Why is that?)
- (Meta) Kernelization
- Bidimensionality and kernels
- Chordal deletion is fixed-parameter tractable
- Randomized parameterized algorithms for \(P_2\)-packing and co-path packing problems
- Planar graph vertex partition for linear problem kernels
- Improved linear problem kernel for planar connected dominating set
- The Parametrized Complexity of Some Fundamental Problems in Coding Theory
- Parameterized complexity of control and bribery for \(d\)-approval elections
- Domination problems in nowhere-dense classes of graphs
- Matching and weighted \(P_2\)-packing: algorithms and kernels
- Connectivity is not a limit for kernelization: planar connected dominating set
- Crown structures for vertex cover kernelization
- Parameterized computational complexity of Dodgson and Young elections
- Contractibility and NP-completeness
- Edge-contraction problems
- A linear kernel for a planar connected dominating set
- Graph-modeled data clustering: Exact algorithms for clique generation
- Parameterized algorithmics for linear arrangement problems
- Fixed-parameter complexity in AI and nonmonotonic reasoning
- The kernelization complexity of connected domination in graphs with (no) small cycles
- Improved parameterized algorithms for minimum link-length rectilinear spanning path problem
- Parameterized Complexity for Domination Problems on Degenerate Graphs
- Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
- Cluster editing: kernelization based on edge cuts
- Radiation hybrid map construction problem parameterized
- Complexity and parameterized algorithms for cograph editing
- A practical exact algorithm for the individual haplotyping problem MEC/GI
Cited In (13)
- Faster deterministic algorithm for \textsc{Co-Path Set}
- Smaller kernels for several FPT problems based on simple observations
- Parameterized algorithms for edge biclique and related problems
- An improved linear kernel for the cycle contraction problem
- An improved FPT algorithm for almost forest deletion problem
- On the parameterized complexity of contraction to generalization of trees
- Kernelization and randomized parameterized algorithms for co-path set problem
- An improved linear kernel for complementary maximal strip recovery: simpler and smaller
- Space-efficient graph kernelizations
- An approximation algorithm for the \(l\)-pseudoforest deletion problem
- Improved PTAS for the constrained \(k\)-means problem
- Dealing with several parameterized problems by random methods
- On the parameterized complexity of contraction to generalization of trees
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)
