19 citations · 54 across the 16 of their papers we have counts for
Showing 2020Show all
2 papers · 1 filter
cs.DS2020★ 1 cited
Constructing Large Matchings via Query Access to a Maximal Matching Oracle
Lidiya Khalidah binti Khalil, Christian Konrad
Multi-pass streaming algorithm for Maximum Matching have been studied since more than 15 years and various algorithmic results are known today, including -pass streaming algorit…
cs.DS2020★ 3 cited
Optimal Lower Bounds for Matching and Vertex Cover in Dynamic Graph Streams
Jacques Dark, Christian Konrad
In this paper, we give simple optimal lower bounds on the one-way two-party communication complexity of approximate Maximum Matching and Minimum Vertex Cover with deletions. In our…