Asosiy kontentga oʻtish
Boshqa

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
Ochiq kirishGibrid

Litsenziya: cc-by

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