1 citations · 1 across the 1 of their papers we have counts for
Showing cs.DSShow all
3 papers · 1 filter
cs.DS2026
Paying for Fractional Error: Tight Constant-Round Approximation of Covering Problems with Short Broadcasts
Saeed Amiri, Sebastian Siebertz, Wojciech Wawrzyniak
We present a general framework for deterministic constant-round approximation of covering problems in sparse networks in the broadcast CONGEST model, where every vertex broadcasts…
cs.DS2026
Near-Optimal Distributed Domination in Planar Graphs
Wojciech Wawrzyniak
We give a deterministic -approximation for minimum dominating set on planar graphs in a constant number of rounds of the LOCAL model, for every . Th…
cs.DS2013★ 1 cited
A local constant-factor approximation algorithm for MDS problem in anonymous network
Wojciech Wawrzyniak
In research on distributed local algorithms it is commonly assumed that each vertex has a unique identifier in the entire graph. However, it turns out that in case of certain class…