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

DOI10.1016/J.DAM.2010.10.004MaRDI QIDQ415281zbMATH OpenOpenAlexFDO

Authors 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 setparameterized complexityplanar graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Planar graphs; geometric and topological aspects of graph theory (05C10)

Recommendations

• A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• scientific article; zbMATH DE number 1929955
• Computational Study on Dominating Set Problem of Planar Graphs
• scientific article; zbMATH DE number 1617251
• A refined search tree technique for dominating set on planar graphs
• New analysis and computational study for the planar connected dominating set problem
• scientific article; zbMATH DE number 1834643
• Dominating sets in planar graphs
• Computational study on planar dominating set problem

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 1929955 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A refined search tree technique for dominating set on planar graphs
• Design by measure and conquer. A faster exact algorithm for dominating set
• Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
• Dynamic Programming and Fast Matrix Multiplication
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• Inclusion/Exclusion Meets Measure and Conquer
• Mathematical Foundations of Computer Science 2004
• Parameterized complexity: exponential speed-up for planar graph problems
• Planar graphs: Theory and algorithms
• Polynomial-time data reduction for dominating set

Cited in

(3)

• scientific article; zbMATH DE number 1617251 (Why is no real title available?)
• scientific article; zbMATH DE number 1929955 (Why is no real title available?)
• A refined search tree technique for dominating set on planar graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q415281)