4 papers · 1 filter
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 -round -approximation LOCAL algorit…
The Distributed Complexity Landscape on Trees Depends on the Knowledge About the Network Size
Alkida Balliu, Sebastian Brandt, Fabian Kuhn +3
One of the central models in distributed computing is Linial's LOCAL model [SIAM J. Comp. 1992]. Over time, researchers have studied distributed graph problems in the LOCAL model u…
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- surface admit a simple -round -approximation distributed algorithm for Minimum Dominating Set…
Local Constant Approximation for Dominating Set on Graphs Excluding Large Minors
Marthe Bonamy, Cyril Gavoille, Timothé Picavet +1
We show that graphs excluding as a minor admit a -round -approximation deterministic distributed algorithm for Minimum Dominating Set. The result extends to Min…