Academic
Publications
Computational Study for Planar Connected Dominating Set Problem

Computational Study for Planar Connected Dominating Set Problem,10.1007/978-3-642-17461-2_9,Marjan Marzban,Qian-Ping Gu,Xiaohua Jia

Computational Study for Planar Connected Dominating Set Problem  
BibTex | RIS | RefWorks Download
The connected dominating set (CDS) problem is a well studied NP-hard problem with many important applications. Dorn et al. [ESA2005, LNCS3669,pp95-106] introduce a new technique to generate 2O(Ö</font >n)2^{O(\sqrt{n})} time and fixed-parameter algorithms for a number of non-local hard problems, including the CDS problem in planar graphs. The practical performance of this algorithm is yet to be evaluated. We perform a computational study for such an evaluation. The results show that the size of instances can be solved by the algorithm mainly depends on the branchwidth of the instances, coinciding with the theoretical result. 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. This suggests that the branch-decomposition based algorithms can be practical for the planar CDS problem.
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.