An efficient algorithm for the k-dominating set problem on very large-scale networks (extended abstract)
- Publisher:
- Springer
- Publication Type:
- Conference Proceeding
- Citation:
- Computational Data and Social Networks (LNCS), 2019, 11917, pp. 74-76
- Issue Date:
- 2019-01-01
Open Access
Copyright Clearance Process
- Recently Added
- In Progress
- Open Access
This item is open access.
© Springer Nature Switzerland AG 2019. The minimum dominating set problem (MDSP) aims to construct the minimum-size subset $$D \subset V$$ of a graph $$G = (V, E)$$ such that every vertex has at least one neighbor in D. The problem is proved to be NP-hard [5]. 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 $$D:k$$. The MkDSP can be used to model applications in social networks [2] and design of wireless sensor networks [3]. 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.
Please use this identifier to cite or link to this item: