2020/12/09 by Sharareh Alipour, Ehsan Futuhi, Alipour, Sharareh +3
Computer Science · #Caching and Content Delivery #Complexity and Algorithms in Graphs #Cooperative Communication and Network Coding #Distributed #FOS: Computer and information sciences #Parallel #Peer-to-Peer Network Technologies #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2012.04883
openalex publication_date 2020/12/09 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
In this paper, we propose a distributed algorithm for the minimum dominating\nset problem. For some especial networks, we prove theoretically that the\nachieved answer by our proposed algorithm is a constant approximation factor of\nthe exact answer. This problem arises naturally in social networks, for example\nin news spreading, avoiding rumor spreading and recommendation spreading. So we\nimplement our algorithm on massive social networks and compare our results with\nthe state of the art algorithms. Also, we extend our algorithm to solve the\nk-distance dominating set problem and experimentally study the efficiency of\nthe proposed algorithm.\n Our proposed algorithm is fast and easy to implement and can be used in\ndynamic networks where the edges and vertices are added or deleted constantly.\nMore importantly, based on the experimental results the proposed algorithm has\nreasonable solutions and running time which enables us to use it in distributed\nmodel practically.\n