Cyril Gavoille

collaborators

Showing cs.DCShow all

2 papers · 1 filter

cs.DC2025

Distributed Approximation Algorithms for Minimum Dominating Set in Locally Nice Graphs

Marthe Bonamy, Cyril Gavoille, Timothé Picavet +1

We give a new, short proof that graphs embeddable in a given Euler genus- $g$ surface admit a simple $f (g)$ -round $α$ -approximation distributed algorithm for Minimum Dominating Set…

cs.DC2025

Local Constant Approximation for Dominating Set on Graphs Excluding Large Minors

Marthe Bonamy, Cyril Gavoille, Timothé Picavet +1

We show that graphs excluding $K_{2, t}$ as a minor admit a $f (t)$ -round $50$ -approximation deterministic distributed algorithm for Minimum Dominating Set. The result extends to Min…