Planar graph vertex partition for linear problem kernels
connected vertex coveredge dominating setkernelizationmaximum triangle packingparameterized algorithm
Planar graphs; geometric and topological aspects of graph theory (05C10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
- 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
- (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
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- 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
- A (3+)k-vertex kernel for edge-disjoint triangle packing
- Maximum matching and kernelization of edge dominating set
- Towards optimal kernel for connected vertex cover in planar graphs
- An improved linear kernel for complementary maximal strip recovery: simpler and smaller
- Linear kernels for separating a graph into components of bounded size
- Towards optimal kernel for edge-disjoint triangle packing
- On the kernelization of split graph problems
- Circumventing connectivity for kernelization
- A new parameterized kernelization algorithm for the planar clique cover problem
- A 13k-kernel for planar feedback vertex set via region decomposition
- Linear problem kernels for planar graph problems with small distance property
- Kernelization of edge perfect code and its variants
- Polynomial kernels for hard problems on disk graphs
- A \(9k\) kernel for nonseparating independent set in planar graphs
- Kernelization of two path searching problems on split graphs
- A 42k kernel for the complementary maximal strip recovery problem
- Solving partition problems almost always requires pushing many vertices around
- Edge domination number and the number of minimum edge dominating sets in pseudofractal scale-free web and Sierpiński gasket
- Improved kernel results for some FPT problems based on simple observations
- A linear kernel for planar red-blue dominating set
- A \(9k\) kernel for nonseparating independent set in planar graphs
- Solving partition problems almost always requires pushing many vertices around
- Linear Problem Kernels for NP-Hard Problems on Planar Graphs
- On the polynomial kernelizations of finding a shortest path with positive disjunctive constraints
- Improved kernels for several problems on planar graphs
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)
