Smaller Kernels for Several FPT Problems Based on Simple Observations

DOI10.1007/978-3-319-19647-3_16zbMath1356.68103OpenAlexW2292973071MaRDI QIDQ3452562

Shuai Hu, Wenjun Li

Publication date: 12 November 2015

Published in: Frontiers in Algorithmics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-19647-3_16

Mathematics Subject Classification ID

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)

Cites Work

• Unnamed Item
• The kernelization complexity of connected domination in graphs with (no) small cycles
• A linear kernel for a planar connected dominating set
• Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
• Parameterized algorithmics for linear arrangement problems
• Contracting graphs to paths and trees
• Domination Problems in Nowhere-Dense Classes
• An Improved Kernel for Planar Connected Dominating Set
• Domination When the Stars Are Out
• Radiation Hybrid Map Construction Problem Parameterized
• Randomized Parameterized Algorithms for Co-path Set Problem
• Chordal Deletion Is Fixed-Parameter Tractable
• Connectivity Is Not a Limit for Kernelization: Planar Connected Dominating Set
• Parameterized Complexity for Domination Problems on Degenerate Graphs
• Obtaining a Bipartite Graph by Contracting Few Edges
• Bidimensionality and Geometric Graphs

This page was built for publication: Smaller Kernels for Several FPT Problems Based on Simple Observations