Planar graph vertex partition for linear problem kernels
DOI10.1016/J.JCSS.2012.08.001zbMATH Open1268.68136OpenAlexW2011167300MaRDI QIDQ355502FDOQ355502
Jianer Chen, Jianxin Wang, Jiong Guo, Yongjie Yang
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
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
kernelizationparameterized algorithmconnected vertex coveredge dominating setmaximum triangle packing
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)
Cites Work
- Title not available (Why is that?)
- A Problem Kernelization for Graph Packing
- Incompressibility through Colors and IDs
- (Meta) Kernelization
- Bidimensionality and Geometric Graphs
- Towards optimal kernel for connected vertex cover in planar graphs
- Polynomial-time data reduction for dominating set
- Linear Problem Kernels for NP-Hard Problems on Planar Graphs
- The parameterized complexity of the induced matching problem
- Connectivity Is Not a Limit for Kernelization: Planar Connected Dominating Set
- Linear Kernel for Planar Connected Dominating Set
- 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
- Kernelization: new upper and lower bound techniques
Cited In (15)
- A \((3+\epsilon)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
- A 42k Kernel for the Complementary Maximal Strip Recovery Problem
- On the kernelization of split graph problems
- Kernelization of edge perfect code and its variants
- Linear kernels for separating a graph into components of bounded size
- Towards optimal kernel for edge-disjoint triangle packing
- EDGE DOMINATION NUMBER AND THE NUMBER OF MINIMUM EDGE DOMINATING SETS IN PSEUDOFRACTAL SCALE-FREE WEB AND SIERPIŃSKI GASKET
- An improved linear kernel for complementary maximal strip recovery: simpler and smaller
- Kernelization of Two Path Searching Problems on Split Graphs
- 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 linear kernel for planar red-blue dominating set
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)
