A linear kernel for planar red-blue dominating set
From MaRDI portal
Publication:516887
DOI10.1016/j.dam.2016.09.045zbMath1358.05217arXiv1408.6388OpenAlexW1670558977MaRDI QIDQ516887
Valentin Garnero, Ignasi Sau, Dimitrios M. Thilikos
Publication date: 15 March 2017
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1408.6388
Planar graphs; geometric and topological aspects of graph theory (05C10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (6)
A Retrospective on (Meta) Kernelization ⋮ Balanced independent and dominating sets on colored interval graphs ⋮ Editing to a Planar Graph of Given Degrees ⋮ Linear kernels for \(k\)-tuple and liar's domination in bounded genus graphs ⋮ Subexponential fixed-parameter algorithms for partial vector domination ⋮ Editing to a planar graph of given degrees
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Planar graph vertex partition for linear problem kernels
- Fundamentals of parameterized complexity
- A linear kernel for a planar connected dominating set
- Parametrized complexity theory.
- Explicit Linear Kernels via Dynamic Programming
- Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
- Connectivity Is Not a Limit for Kernelization: Planar Connected Dominating Set
- Polynomial-time data reduction for dominating set
- Incompressibility through Colors and IDs
- Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
- (Meta) Kernelization
- Bidimensionality and Geometric Graphs
- Linear Problem Kernels for NP-Hard Problems on Planar Graphs
This page was built for publication: A linear kernel for planar red-blue dominating set
