13 citations · 17 across the 2 of their papers we have counts for
Showing cs.DSShow all
3 papers · 1 filter
cs.DS2020★ 1 cited
Improved 3-pass Algorithm for Counting 4-cycles in Arbitrary Order Streaming
Sofya Vorotnikova
The problem of counting small subgraphs, and specifically cycles, in the streaming model received a lot of attention over the past few years. In this paper, we consider arbitrary o…
cs.DS2015★ 4 cited
Densest Subgraph in Dynamic Graph Streams
Andrew McGregor, David Tench, Sofya Vorotnikova +1
In this paper, we consider the problem of approximating the densest subgraph in the dynamic graph stream model. In this model of computation, the input graph is defined by an arbit…
cs.DS2015★ 13 cited
Kernelization via Sampling with Applications to Dynamic Graph Streams
Rajesh Chitnis, Graham Cormode, Hossein Esfandiari +4
In this paper we present a simple but powerful subgraph sampling primitive that is applicable in a variety of computational models including dynamic graph streams (where the input…