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

Marjan Marzban (), Qian-Ping Gu () and Xiaohua Jia ()
Additional contact information
Marjan Marzban: Simon Fraser University
Qian-Ping Gu: Simon Fraser University
Xiaohua Jia: City University of Hong Kong

Journal of Combinatorial Optimization, 2016, vol. 32, issue 1, No 13, 198-225

Abstract: Abstract 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(2^{9.822\sqrt{n}}n+n^3)$$ O ( 2 9.822 n n + n 3 ) time and $$O(2^{8.11\sqrt{n}}n+n^3)$$ O ( 2 8.11 n n + n 3 ) 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(2^{9.8\sqrt{n}}n+n^3)$$ O ( 2 9.8 n n + n 3 ) time with a conventional method and in $$O(2^{8.08\sqrt{n}}n+n^3)$$ O ( 2 8.08 n n + n 3 ) time with a fast matrix multiplication. For a graph $$G$$ G , let $${\hbox {bw}}(G)$$ bw ( G ) be the branchwidth of $$G$$ G and $$\gamma _c(G)$$ γ c ( G ) be the connected dominating number of $$G$$ G . We prove $${\hbox {bw}}(G)\le 2\sqrt{10\gamma _c(G)}+32$$ bw ( G ) ≤ 2 10 γ c ( G ) + 32 . From this result, the planar CDS problem admits an $$O(2^{23.54\sqrt{\gamma _c(G)}}\gamma _c(G)+n^3)$$ O ( 2 23.54 γ c ( G ) γ c ( G ) + n 3 ) 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.

Keywords: Branch-decomposition based algorithms; Connected dominating set; Planar graphs; Fixed-parameter algorithms; Computational study (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-015-9871-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:32:y:2016:i:1:d:10.1007_s10878-015-9871-0

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-015-9871-0

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().