3 citations · 6 across the 3 of their papers we have counts for
5 papers · 1 filter
Streaming Maximal Matching with Bounded Deletions
Sanjeev Khanna, Christian Konrad, Jacques Dark
We initiate the study of the Maximal Matching problem in bounded-deletion graph streams. In this setting, a graph is revealed as an arbitrary sequence of edge insertions and de…
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…
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…
Fast Sketch-based Recovery of Correlation Outliers
Graham Cormode, Jacques Dark
Many data sources can be interpreted as time-series, and a key problem is to identify which pairs out of a large collection of signals are highly correlated. We expect that there w…
Independent Set Size Approximation in Graph Streams
Graham Cormode, Jacques Dark, Christian Konrad
We study the problem of estimating the size of independent sets in a graph defined by a stream of edges. Our approach relies on the Caro-Wei bound, which expresses the desired…