47 citations · 138 across the 17 of their papers we have counts for
Showing 2012Show all
2 papers · 1 filter
cs.DC2012★ 4 cited
No Sublogarithmic-time Approximation Scheme for Bipartite Vertex Cover
Mika Göös, Jukka Suomela
König's theorem states that on bipartite graphs the size of a maximum matching equals the size of a minimum vertex cover. It is known from prior work that for every ε> 0 there exis…
cs.DC2012★ 47 cited
Lower Bounds for Local Approximation
Mika Göös, Juho Hirvonen, Jukka Suomela
In the study of deterministic distributed algorithms it is commonly assumed that each node has a unique -bit identifier. We prove that for a general class of graph probl…