检索结果-内蒙古大学图书馆

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

JOURNAL OF COMBINATORIAL OPTIMIZATION 2016年第1期32卷 198-225页

作者： Marzban, Marjan Gu, Qian-Ping Jia, Xiaohua Simon Fraser Univ Sch Comp Sci Burnaby BC V5A 1S6 Canada City Univ Hong Kong Dept Comp Sci Kowloon Hong Kong Peoples R China

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 time and 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 time with a conventional method and in time with a fast matrix multiplication. For a graph , let be the branchwidth of and be the connected dominating number of . We prove . From this result, the planar CDS problem admits an 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.

关键词： branch-decomposition based algorithms Connected dominating set Planar graphs Fixed-parameter algorithms Computational study

来源：评论

学校读者我要写书评

暂无评论

Computational Study on a PTAS for Planar Dominating Set Problem

引用

algorithms 2013年第1期6卷 43-59页

作者： Marzban, Marjan Gu, Qian-Ping Simon Fraser Univ Sch Comp Sci Burnaby BC V5A 1S6 Canada

The dominating set problem is a core NP-hard problem in combinatorial optimization and graph theory, and has many important applications. Baker [JACM 41,1994] introduces a k-outer planar graph decomposition-based framework for designing polynomial time approximation scheme (PTAS) for a class of NP-hard problems in planar graphs. It is mentioned that the framework can be applied to obtain an O(2(ck)n) time, c is a constant, (1+1/k)-approximation algorithm for the planar dominating set problem. We show that the approximation ratio achieved by the mentioned application of the framework is not bounded by any constant for the planar dominating set problem. We modify the application of the framework to give a PTAS for the planar dominating set problem. With k-outer planar graph decompositions, the modified PTAS has an approximation ratio (1 + 2/k). Using 2k-outer planar graph decompositions, the modified PTAS achieves the approximation ratio (1+1/k) in O(2(2ck)n) time. We report a computational study on the modified PTAS. Our results show that the modified PTAS is practical.

关键词： dominating set problem PTAS branch-decomposition based algorithms planar graphs computational study

来源：评论

学校读者我要写书评

暂无评论

Computational Study for Planar Connected Dominating Set Problem

Computational Study for Planar Connected Dominating Set Prob...

引用

4th Annual International Conference on Combinatorial Optimization and Applications (COCOA)

作者： Marzban, Marjan Gu, Qian-Ping Jia, Xiaohua Simon Fraser Univ Sch Comp Sci Burnaby BC V5A 1S6 Canada City Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China

ISBN: (纸本)9783642174605

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 2(O)(root 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.

关键词： branch-decomposition based algorithms CDS problem planar graphs fixed-parameter algorithms computational study

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：