46 citations · 166 across the 16 of their papers we have counts for
Showing cs.DCShow all
2 papers · 1 filter
cs.DC2010★ 17 cited
Local algorithms in (weakly) coloured graphs
Matti Åstrand, Valentin Polishchuk, Joel Rybicki +2
A local algorithm is a distributed algorithm that completes after a constant number of synchronous communication rounds. We present local approximation algorithms for the minimum d…
cs.DC2008★ 43 cited
A simple local 3-approximation algorithm for vertex cover
Valentin Polishchuk, Jukka Suomela
We present a local algorithm (constant-time distributed algorithm) for finding a 3-approximate vertex cover in bounded-degree graphs. The algorithm is deterministic, and no auxilia…