Skip to content
image post
White papers

Solving the k-dominating set problem on very large-scale networks

April 16, 2024

Share with:


Authors: Minh Hai Nguyen, Minh Hoàng Hà, Diep N. Nguyen & The Trung Tran 

Abstract: The well-known minimum dominating set problem (MDSP) aims to construct the minimum-size subset of vertices in a graph such that every other vertex has at least one neighbor in the subset. In this article, we study a general version of the problem that extends the neighborhood relationship: two vertices are called neighbors of each other if there exists a path through no more than k edges between them. The problem called “minimum k-dominating set problem” (MkDSP) becomes the classical dominating set problem if k is 1 and has important applications in monitoring large-scale social networks. We propose an efficient heuristic algorithm that can handle real-world instances with up to 17 million vertices and 33 million edges. This is the first time such large graphs are solved for the minimum k-dominating set problem.

Published: 20 July 2020


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!