Recently, there has been a lot of interest and progress in lowering the worst-case time complexity for the PLANAR DOMINATING SET problem. In this paper, we present improved parameterized algorithms for the PLANAR DOMINATING SET problem. In particular, given a planar graph G and a positive integer k, we can compute a dominating set of size bounded by k or report that no such set exists in time O(2 27 n), where n is the number of vertices in G. Our algorithms induce a significant improvement over the previous best algorithm for the problem.
['Iyad A. Kanj', 'Ljubomir Perkovic']
Improved parameterized algorithms for planar dominating set