Algorithms for the minimum weight k‐fold (connected) dominating set problem

0.00 Avg rating—0 Votes

Article ID:	iaor20123738
Volume:	23
Issue:	4
Start Page Number:	528
End Page Number:	540
Publication Date:	May 2012
Journal:	Journal of Combinatorial Optimization
Authors:	Zhang Zhao, Li Deying, Ma Wenkai
Keywords:	combinatorial optimization, programming: dynamic

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.

Reviews

Required fields are marked *. Your email address will not be published.