9 citations · 25 across the 8 of their papers we have counts for
12 papers · 1 filter
On Two-Pass Streaming Algorithms for Maximum Bipartite Matching
Christian Konrad, Kheeran K. Naidu
We study two-pass streaming algorithms for Maximum Bipartite Matching (MBM). All known two-pass streaming algorithms for MBM operate in a similar fashion: They compute a maximal ma…
Robust Lower Bounds for Graph Problems in the Blackboard Model of Communication
Christian Konrad, Peter Robinson, Viktor Zamaraev
We give lower bounds on the communication complexity of graph problems in the multi-party blackboard model. In this model, the edges of an -vertex input graph are partitioned am…
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…
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…
Frequent Elements with Witnesses in Data Streams
Christian Konrad
Detecting frequent elements is among the oldest and most-studied problems in the area of data streams. Given a stream of data items in , the objective is to…
Independent Sets in Vertex-Arrival Streams
Graham Cormode, Jacques Dark, Christian Konrad
We consider the classic maximal and maximum independent set problems in three models of graph streams: In the edge-arrival model we see a stream of edges which collectively define…