论文标题
从理论到应用
On Distributed Algorithms for Minimum Dominating Set problem, from theory to application
论文作者
论文摘要
在本文中，我们提出了一种针对最低主导设置问题的分布式算法。对于某些特别的网络，我们从理论上证明了通过我们提出的算法所达到的答案是确切答案的恒定近似因素。这个问题自然出现在社交网络中，例如在新闻传播中，避免谣言传播和推荐传播。因此，我们在大规模的社交网络上实施算法，并将结果与最先进的算法进行比较。此外，我们扩展了算法来解决$ k $ distance主导的设置问题，并实验研究所提出算法的效率。 我们提出的算法快速且易于实现，可以在不断添加或不断添加边缘和顶点的动态网络中使用。更重要的是，根据实验结果，提出的算法具有合理的解决方案和运行时间，使我们能够实际上在分布式模型中使用它。
In this paper, we propose a distributed algorithm for the minimum dominating set problem. For some especial networks, we prove theoretically that the achieved answer by our proposed algorithm is a constant approximation factor of the exact answer. This problem arises naturally in social networks, for example in news spreading, avoiding rumor spreading and recommendation spreading. So we implement our algorithm on massive social networks and compare our results with the state of the art algorithms. Also, we extend our algorithm to solve the $k$-distance dominating set problem and experimentally study the efficiency of the proposed algorithm. Our proposed algorithm is fast and easy to implement and can be used in dynamic networks where the edges and vertices are added or deleted constantly. More importantly, based on the experimental results the proposed algorithm has reasonable solutions and running time which enables us to use it in distributed model practically.
