19 citations · 54 across the 16 of their papers we have counts for
3 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…
The Complexity of Symmetry Breaking in Massive Graphs
Christian Konrad, Sriram V. Pemmaraju, Talal Riaz +1
The goal of this paper is to understand the complexity of symmetry breaking problems, specifically maximal independent set (MIS) and the closely related -ruling set problem, in…
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…