未找到相关数据
Algorithms for the minimum weight k-fold (connected) dominating set problem
被引：0
作者：
Wenkai Ma
Deying Li
Zhao Zhang
机构：
[1] Renmin University of China,Key Laboratory of Data Engineering and Knowledge Engineering, MOE, School of Information
[2] Xinjiang University,College of Mathematics and System Sciences
来源：
Journal of Combinatorial Optimization
|
2012年
/
23卷
关键词：
-fold dominating set;
Slab decomposition;
Algorithm;
Unit ball graph;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
In this paper, we study the problem of computing a minimum weight k-fold dominating set (MWkDS) or a minimum weight k-fold connected dominating set (MWkCDS) in a unit ball graph (UBG). Using slab decomposition and dynamic programming, we give two exact algorithms for the computation of MWkDS and MWkCDS which can be executed in polynomial time if the thickness of the graph is bounded above.
引用
收藏
页码：528 / 540
页数：12
相关论文
未找到相关数据