论文标题
稀疏图上的分布式统治
Distributed domination on sparse graph classes
论文作者
论文摘要
我们表明，主体集问题在具有界膨胀的图形类别的局部分布式计算中，在恒定的圆形模型中允许恒定因子近似值。这概括了Czygrinow等人的结果。对于具有排除拓扑未成年人的图形，可统一的稀疏图。我们演示了如何对我们的一般算法进行修改和微调以计算平面图上最低统治设置的（$ 11+ε$） - 近似（对于任何$ε> 0）$。这在平面图上的先前最著名的近似因子为52，这是通过Lenzen等人的优雅而简单的算法实现的。
We show that the dominating set problem admits a constant factor approximation in a constant number of rounds in the LOCAL model of distributed computing on graph classes with bounded expansion. This generalizes a result of Czygrinow et al. for graphs with excluded topological minors to very general classes of uniformly sparse graphs. We demonstrate how our general algorithm can be modified and fine-tuned to compute an ($11+ε$)-approximation (for any $ε>0)$ of a minimum dominating set on planar graphs. This improves on the previously best known approximation factor of 52 on planar graphs, which was achieved by an elegant and simple algorithm of Lenzen et al.
