Simpler Linear-Time Kernelization for Planar Dominating Set

DOI10.1007/978-3-642-28050-4_15zbMath1352.68109OpenAlexW1768174637MaRDI QIDQ2891347

Torben Hagerup

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

Mathematics Subject Classification ID

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