13 citations · 20 across the 5 of their papers we have counts for
6 papers
Vertex Ordering Problems in Directed Graph Streams
Amit Chakrabarti, Prantar Ghosh, Andrew McGregor +1
We consider directed graph algorithms in a streaming setting, focusing on problems concerning orderings of the vertices. This includes such fundamental problems as topological sort…
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…
Storage Capacity as an Information-Theoretic Vertex Cover and the Index Coding Rate
Arya Mazumdar, Andrew McGregor, Sofya Vorotnikova
Motivated by applications in distributed storage, the storage capacity of a graph was recently defined to be the maximum amount of information that can be stored across the vertice…
A Note on Logarithmic Space Stream Algorithms for Matchings in Low Arboricity Graphs
Andrew McGregor, Sofya Vorotnikova
We present a data stream algorithm for estimating the size of the maximum matching of a low arboricity graph. Recall that a graph has arboricity if its edges can be partitioned…
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…
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…