Marthe Bonamy

most cited

χ

-Boundedness and Neighbourhood Complexity of Bounded Merge-Width Graphs

1 citations · 1 across the 6 of their papers we have counts for

collaborators

Showing cs.DCShow all

3 papers · 1 filter

cs.DC2026

Meta-Theorems for Cuttable Distributed Problems

Marthe Bonamy, Avinandan Das, Cyril Gavoille +3

We prove that given any $α$ -approximation LOCAL algorithm for Minimum Dominating Set (MDS) on planar graphs, we can construct an $f (g)$ -round $(3 α + 1)$ -approximation LOCAL algorithm…

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…