Distributed Dominating Set With Optimal Rounds and Message Size in Bounded Arboricity Graphs
Sharareh AlipourTehran Institute for Advanced Studies (TeIAS), Tehran, IranErmiya FarokhnejadUniversity of Warwick, Coventry, United Kingdom
2026
ABI
Annotatsiya
We study the distributed minimum dominating set problem on graphs of arboricity α. Dory, Ghaffari, and Ilchi [PODC'22] showed that any algorithm achieving a constant or poly-logarithmic approximation factor needs at least Ω(log Δ/log log Δ) rounds in graphs of maximum degree Δ and arboricity α, even when α = 2 and even when the message sizes are unbounded. Although there is a variety of algorithms with a near-optimal round complexity of O(log Δ), it is natural to ask: What is the best approximation factor in the optimal round complexity of O(log Δ/log log Δ)?
Hali tarjima qilinmagan
Identifikatorlar
Iqtiboslar va manbalar
0 ta iqtibos46 ta foydalanilgan manba