A strengthened analysis of an algorithm for Dominating Set in planar graphs

Alber et al. presented an algorithm for computing a dominating set of size at most kk, if one exists, in an undirected planar nn-vertex graph and bounded its execution time by O(8kn)O(8kn). Here it is shown that the algorithm performs better than claimed by its authors. More significantly, if k≤n/19k≤n/19, even a much simplified version of the algorithm runs in O(7kn)O(7kn) time.