Improved kernel results for some FPT problems based on simple observations
From MaRDI portal
Publication:507431
DOI10.1016/j.tcs.2016.06.012zbMath1356.68102OpenAlexW2425261484MaRDI QIDQ507431
Qilong Feng, Shuai Hu, Wenjun Li, Jian'er 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
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items
Dealing with several parameterized problems by random methods, Parameterized algorithms for edge biclique and related problems, Faster deterministic algorithm for \textsc{Co-Path Set}, Improved PTAS for the constrained \(k\)-means problem, 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, On the Parameterized Complexity of Contraction to Generalization of Trees.
Cites Work
- Unnamed Item
- Unnamed Item
- Planar graph vertex partition for linear problem kernels
- Improved linear problem kernel for planar connected dominating set
- Matching and weighted \(P_2\)-packing: algorithms and kernels
- The kernelization complexity of connected domination in graphs with (no) small cycles
- Improved parameterized algorithms for minimum link-length rectilinear spanning path problem
- A linear kernel for a planar connected dominating set
- Complexity and parameterized algorithms for cograph editing
- Finding odd cycle transversals.
- Edge-contraction problems
- Graph-modeled data clustering: Exact algorithms for clique generation
- A practical exact algorithm for the individual haplotyping problem MEC/GI
- Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
- Chordal deletion is fixed-parameter tractable
- Parameterized algorithmics for linear arrangement problems
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Fixed-parameter complexity in AI and nonmonotonic reasoning
- Cluster editing: kernelization based on edge cuts
- Parameterized computational complexity of Dodgson and Young elections
- Randomized parameterized algorithms for \(P_2\)-packing and co-path packing problems
- Parameterized complexity of control and bribery for \(d\)-approval elections
- Radiation hybrid map construction problem parameterized
- Contracting graphs to paths and trees
- Crown structures for vertex cover kernelization
- Domination Problems in Nowhere-Dense Classes
- Connectivity Is Not a Limit for Kernelization: Planar Connected Dominating Set
- Contractibility and NP-completeness
- Color-coding
- The Parametrized Complexity of Some Fundamental Problems in Coding Theory
- (Meta) Kernelization
- Parameterized Complexity for Domination Problems on Degenerate Graphs
- Bidimensionality and Geometric Graphs
