In this paper, we study the minimum dominating set (MDS) problem and the minimum total dominating set MTDS) problem which have many applications in real world. We propose a new idea to compute approximate MDS and MTDS. Next, we give an upper bound on the size of MDS of a graph. We also present a distributed randomized algorithm that produces a (total) dominating subset of a given graph whose expected size equals the upper bound. Next, we give fast distributed algorithms for computing approximated solutions for the MDS and MTDS problems using our theoretical results. The MDS problem arises in diverse areas, for example in social networks, wireless networks, robotics, and etc. Most often, we need to compute MDS in a distributed or parallel model. So we implement our algorithm on massive networks and compare our results with the state of the art algorithms to show the efficiency of our proposed algorithms in practice. We also show how to extend our idea to propose algorithms for solving $k$-dominating set problem and set cover problem. Our algorithms can also handle the case where the network is dynamic or in the case where we have constraints in choosing the elements of MDS.

翻译：在本文中, 我们研究在现实世界中有许多应用的最小占位集( MDS) 问题和最小总占位集 MTDS 问题。 我们提出一个新的想法来计算近似 MDS 和 MTDS 。 下一步, 我们给一个图形的MDS 大小设定一个上限。 我们还提出一个分布式随机算法, 产生一个( 总计) 占位集子, 这个图的预期尺寸等于上限的某个特定图。 其次, 我们提供快速分布式算法, 利用我们的理论结果计算MDS 和 MTDS 问题的近似解决方案。 MDS 问题出现在不同的领域, 例如社交网络、 无线网络、 机器人等等。 最经常的情况是, 我们需要在分布式或平行式模型中计算 MDS 。 所以我们在大型网络上执行我们的算法, 并将我们的结果与艺术算法的状态进行比较, 以显示我们实际中的拟议算法的效率 。 我们还展示如何扩大我们的想法, 提出解决 美元占位集的问题和设置问题的算法 。 我们的算法还可以处理网络中具有动态或MDL 制约要素的案例 。