47 citations · 138 across the 17 of their papers we have counts for
4 papers · 1 filter
Linear-in- Lower Bounds in the LOCAL Model
Mika Göös, Juho Hirvonen, Jukka Suomela
By prior work, there is a distributed algorithm that finds a maximal fractional matching (maximal edge packing) in rounds, where is the maximum degree of the graph. We s…
What can be decided locally without identifiers?
Pierre Fraigniaud, Mika Göös, Amos Korman +1
Do unique node identifiers help in deciding whether a network has a prescribed property ? We study this question in the context of distributed local decision, where the obje…
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…
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…