Algorithms for the minimum weight k-fold (connected) dominating set problem |
| |
| Authors: | Wenkai Ma Deying Li Zhao Zhang |
| |
| Institution: | 1. Key Laboratory of Data Engineering and Knowledge Engineering, MOE, School of Information, Renmin University of China, Beijing, 100872, China
2. College of Mathematics and System Sciences, Xinjiang University, Urumqi, Xinjiang, China
|
| |
| Abstract: | 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. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
