English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The Minimum Dominating Set (MDS) problem is not only one of the mostfundamental problems in distributed computing, it is also one of the mostchallenging ones. While it is well-known that minimum dominating sets cannot beapproximated locally on general graphs, over the last years, severalbreakthroughs have been made on computing local approximations on sparsegraphs.  This paper presents a deterministic and local constant factor approximationfor minimum dominating sets on bounded genus graphs, a very large family ofsparse graphs. Our main technical contribution is a new analysis of a slightlymodified, first-order definable variant of an existing algorithm by Lenzen etal. Interestingly, unlike existing proofs for planar graphs, our analysis doesnot rely on any topological arguments. We believe that our techniques can beuseful for the study of local problems on sparse graphs beyond the scope ofthis paper.

A local constant factor approximation for the minimum dominating set problem on bounded genus graphs