A linear kernel for planar red-blue dominating set

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

zbMATH Keywords

planar graphsparameterized complexitylinear kernelsred-blue domination

Mathematics Subject Classification ID

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