Linear-Time Computation of a Linear Problem Kernel for Dominating Set on Planar Graphs

DOI10.1007/978-3-642-28050-4_16zbMath1352.68119OpenAlexW1505075508MaRDI QIDQ2891348

Rolf Niedermeier, Frank Kammer, Sepp Hartung, René van Bevern, Mathias Weller

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_16

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)

Simpler Linear-Time Kernelization for Planar Dominating Set ⋮ 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

• Local search: is brute-force avoidable?
• Subexponential parameterized algorithms
• Experiments on data reduction for optimal domination in networks
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• Approximation schemes for steiner forest on planar graphs and graphs of bounded treewidth
• Simpler Linear-Time Kernelization for Planar Dominating Set
• Linear Problem Kernels for Planar Graph Problems with Small Distance Property
• Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
• Polynomial-time data reduction for dominating set
• Kernelization: New Upper and Lower Bound Techniques
• Approximation algorithms for NP-complete problems on planar graphs
• (Meta) Kernelization
• Bidimensionality and Geometric Graphs
• Linear Problem Kernels for NP-Hard Problems on Planar Graphs
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Linear-Time Computation of a Linear Problem Kernel for Dominating Set on Planar Graphs