Skip to content
image post
White papers

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

April 16, 2024

Share with:


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 now

Do you need a workthrough of our platform? Let us know

    Related Posts

    Get ahead with AI-powered technology updates!

    Subscribe now to our newsletter for exclusive insights, expert analysis, and cutting-edge developments delivered straight to your inbox!