Planar graph vertex partition for linear problem kernels

DOI10.1016/J.JCSS.2012.08.001MaRDI QIDQ355502zbMATH OpenOpenAlexFDO

Authors Jianxin Wang, Yongjie Yang, Jiong Guo, Jianer Chen

Publication date 24 July 2013

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2012.08.001

zbMATH Keywords

kernelizationparameterized algorithmconnected vertex coveredge dominating setmaximum triangle packing

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Linear problem kernels for planar graph problems with small distance property
• Linear Problem Kernels for NP-Hard Problems on Planar Graphs
• An improved kernel for planar connected dominating set
• Improved linear problem kernel for planar connected dominating set
• Linear-time computation of a linear problem kernel for dominating set on planar graphs

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• (Meta) Kernelization
• A Problem Kernelization for Graph Packing
• An improved kernel for planar connected dominating set
• Bidimensionality and kernels
• Connectivity is not a limit for kernelization: planar connected dominating set
• Fixed-parameter tractability results for full-degree spanning tree and its dual
• Incompressibility through Colors and IDs
• Kernelization: new upper and lower bound techniques
• Linear Kernel for Planar Connected Dominating Set
• Linear Problem Kernels for NP-Hard Problems on Planar Graphs
• New Parameterized Algorithms for the Edge Dominating Set Problem
• Polynomial-time data reduction for dominating set
• The parameterized complexity of the induced matching problem
• Towards optimal kernel for connected vertex cover in planar graphs

Cited in

(23)

• A new parameterized kernelization algorithm for the planar clique cover problem
• Kernelization of two path searching problems on split graphs
• A (3+)k-vertex kernel for edge-disjoint triangle packing
• Maximum matching and kernelization of edge dominating set
• A 13k-kernel for planar feedback vertex set via region decomposition
• Linear problem kernels for planar graph problems with small distance property
• Linear Problem Kernels for NP-Hard Problems on Planar Graphs
• Kernelization of edge perfect code and its variants
• A 42k Kernel for the Complementary Maximal Strip Recovery Problem
• On the kernelization of split graph problems
• Solving partition problems almost always requires pushing many vertices around
• Linear kernels for separating a graph into components of bounded size
• Towards optimal kernel for edge-disjoint triangle packing
• An improved linear kernel for complementary maximal strip recovery: simpler and smaller
• Towards optimal kernel for connected vertex cover in planar graphs
• Circumventing connectivity for kernelization
• Improved kernel results for some FPT problems based on simple observations
• A \(9k\) kernel for nonseparating independent set in planar graphs
• Improved kernels for several problems on planar graphs
• A linear kernel for planar red-blue dominating set
• A \(9k\) kernel for nonseparating independent set in planar graphs
• Polynomial kernels for hard problems on disk graphs
• Edge domination number and the number of minimum edge dominating sets in pseudofractal scale-free web and Sierpiński gasket

This page was built for publication: Planar graph vertex partition for linear problem kernels

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q355502)