A strengthened analysis of an algorithm for dominating set in planar graphs

DOI10.1016/j.dam.2010.10.004zbMath1238.05195OpenAlexW1987342271MaRDI QIDQ415281

Torben Hagerup

Publication date: 11 May 2012

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2010.10.004

zbMATH Keywords

dominating setplanar graphparameterized complexity

Mathematics Subject Classification ID

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)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Planar graphs: Theory and algorithms
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• A refined search tree technique for dominating set on planar graphs
• Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
• Polynomial-time data reduction for dominating set
• Inclusion/Exclusion Meets Measure and Conquer
• Parameterized complexity: exponential speed-up for planar graph problems
• Mathematical Foundations of Computer Science 2004
• Dynamic Programming and Fast Matrix Multiplication

This page was built for publication: A strengthened analysis of an algorithm for dominating set in planar graphs