On the communication and streaming complexity of maximum bipartite matching¶
Goel, K., Kapralov, M., & Khanna, S. (2012). On the communication and streaming complexity of maximum bipartite matching. ACM.
Cited by¶
1 citation across 1 artifact.
Each citation links to the sentence it supports in the citing article.
Domain-specific¶
- Ruzsa–Szemerédi Problem
- Dense Ruzsa–Szemerédi graphs provide hard communication instances and govern bounds for graph-streaming matching approximations
This sourceShows that the smallest epsilon-matching cover of a graph is essentially the size of the largest epsilon-Ruzsa-Szemeredi graph on the same vertex set, and uses that to prove superlinear communication and one-pass streaming lower bounds for better-than-2/3 bipartite matching approximation.
- Dense Ruzsa–Szemerédi graphs provide hard communication instances and govern bounds for graph-streaming matching approximations
Verification¶
This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.
Registry ID ref:a25e24472d85 · see in the full table