19 citations · 54 across the 16 of their papers we have counts for
21 papers
Improved Weighted Matching in the Sliding Window Model
Cezar-Mihail Alexandru, Pavel Dvořák, Christian Konrad +1
We consider the Maximum-weight Matching (MWM) problem in the streaming sliding window model of computation. In this model, the input consists of a sequence of weighted edges on a g…
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…
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…