most citedApproximating Semi-Matchings in Streaming and in Two-Party Communication

9 citations · 9 across the 1 of their papers we have counts for

collaborators

1 paper

cs.DS2013★ 9 cited

Approximating Semi-Matchings in Streaming and in Two-Party Communication

Christian Konrad, Adi Rosén

We study the communication complexity and streaming complexity of approximating unweighted semi-matchings. A semi-matching in a bipartite graph G = (A, B, E), with n = |A|, is a su…