An Efficient Algorithm for the k-Dominating Set Problem on Very Large-Scale Networks (Extended Abstract)

Authors: Tran The Trung, Nguyen Minh Hai, Ha Minh Hoang, Hoang Thai Dinh, Eryk Dutkiewicz, Diep N. Nguyen

Abstract: The minimum dominating set problem (MDSP) aims to construct the minimum-size subset D⊂VD⊂V of a graph G=(V,E)G=(V,E) such that every vertex has at least one neighbor in D. The problem is proved to be NP-hard. In a recent industrial application, we encountered a more general variant of MDSP that extends the neighborhood relationship as follows: a vertex is a k-neighbor of another if there exists a linking path through no more than k edges between them. This problem is called the minimum k-dominating set problem (MkDSP) and the dominating set is denoted as DkDk. The MkDSP can be used to model applications in social networks and design of wireless sensor networks. In our case, a telecommunication company uses the problem model to supervise a large social network up to 17 millions nodes via a dominating subset in which k is set to 3.

Published: 11 November 2019

Part of the Lecture Notes in Computer Science book series (LNCS, volume 11917)

Download: https://link.springer.com/chapter/10.1007/978-3-030-34980-6_9