Simpler Linear-Time Kernelization for Planar Dominating Set
From MaRDI portal
Publication:2891347
DOI10.1007/978-3-642-28050-4_15zbMath1352.68109OpenAlexW1768174637MaRDI QIDQ2891347
Publication date: 15 June 2012
Published in: Parameterized and Exact Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-28050-4_15
Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (6)
Linear-Time Computation of a Linear Problem Kernel for Dominating Set on Planar Graphs ⋮ Extending the kernel for planar Steiner tree to the number of Steiner vertices ⋮ Towards optimal and expressive kernelization for \(d\)-hitting set ⋮ Fixed-parameter algorithms for DAG partitioning ⋮ Capacitated domination: problem complexity and approximation algorithms ⋮ A linear-time kernelization for the rooted \(k\)-leaf outbranching problem
Cites Work
- Unnamed Item
- Unnamed Item
- Planar graphs: Theory and algorithms
- Applying modular decomposition to parameterized cluster editing problems
- Linear-Time Computation of a Linear Problem Kernel for Dominating Set on Planar Graphs
- Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
- Polynomial-time data reduction for dominating set
- (Meta) Kernelization
- Linear Problem Kernels for NP-Hard Problems on Planar Graphs
- Kernelization for Maximum Leaf Spanning Tree with Positive Vertex Weights
This page was built for publication: Simpler Linear-Time Kernelization for Planar Dominating Set