New analysis and computational study for the planar connected dominating set problem

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

View graph of relations


Related Research Unit(s)


Original languageEnglish
Pages (from-to)198-225
Journal / PublicationJournal of Combinatorial Optimization
Issue number1
Publication statusPublished - 1 Jul 2016


The connected dominating set (CDS) problem is a well studied NP-hard problem with many important applications. Dorn et al. (Algorithmica 58:790–810 2010) introduce a branch-decomposition based algorithm design technique for NP-hard problems in planar graphs and give an algorithm (DPBF algorithm) which solves the planar CDS problem in O(29.822nn+n3) time and O(28.11nn+n3) time, with a conventional method and fast matrix multiplication in the dynamic programming step of the algorithm, respectively. We show that DPBF algorithm solves the planar CDS problem in O(29.8nn+n3) time with a conventional method and in O(28.08nn+n3) time with a fast matrix multiplication. For a graph G, let bw (G) be the branchwidth of G and γc(G) be the connected dominating number of G. We prove bw(G)≤210γc(G)+32. From this result, the planar CDS problem admits an O(223.54γc(G)γc(G)+n3) time fixed-parameter algorithm. We report computational study results on the practical performance of DPBF algorithm, which show that the size of instances can be solved by the algorithm mainly depends on the branchwidth of the instances, coinciding with the theoretical analysis. For graphs with small or moderate branchwidth, the CDS problem instances with size up to a few thousands edges can be solved in a practical time and memory space.

Research Area(s)

  • Branch-decomposition based algorithms, Computational study, Connected dominating set, Fixed-parameter algorithms, Planar graphs