Planar graph vertex partition for linear problem kernels

DOI10.1016/j.jcss.2012.08.001zbMath1268.68136OpenAlexW2011167300MaRDI QIDQ355502

Jianxin Wang, Jiong Guo, Yongjie Yang, Jian'er 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

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

Related Items (14)

A \((3+\epsilon)k\)-vertex kernel for edge-disjoint triangle packing ⋮ A \(13k\)-kernel for planar feedback vertex set via region decomposition ⋮ Kernelization of edge perfect code and its variants ⋮ On the kernelization of split graph problems ⋮ Circumventing connectivity for kernelization ⋮ Towards optimal kernel for connected vertex cover in planar graphs ⋮ Towards optimal kernel for edge-disjoint triangle packing ⋮ Kernelization of Two Path Searching Problems on Split Graphs ⋮ A 42k Kernel for the Complementary Maximal Strip Recovery Problem ⋮ Improved kernel results for some FPT problems based on simple observations ⋮ A linear kernel for planar red-blue dominating set ⋮ Maximum matching and kernelization of edge dominating set ⋮ An improved linear kernel for complementary maximal strip recovery: simpler and smaller ⋮ EDGE DOMINATION NUMBER AND THE NUMBER OF MINIMUM EDGE DOMINATING SETS IN PSEUDOFRACTAL SCALE-FREE WEB AND SIERPIŃSKI GASKET

Cites Work

• Unnamed Item
• The parameterized complexity of the induced matching problem
• Towards optimal kernel for connected vertex cover in planar graphs
• An Improved Kernel for Planar Connected Dominating Set
• Fixed-parameter tractability results for full-degree spanning tree and its dual
• New Parameterized Algorithms for the Edge Dominating Set Problem
• Connectivity Is Not a Limit for Kernelization: Planar Connected Dominating Set
• Polynomial-time data reduction for dominating set
• A Problem Kernelization for Graph Packing
• Linear Kernel for Planar Connected Dominating Set
• Incompressibility through Colors and IDs
• Kernelization: New Upper and Lower Bound Techniques
• (Meta) Kernelization
• Bidimensionality and Geometric Graphs
• Linear Problem Kernels for NP-Hard Problems on Planar Graphs

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