Name
Abstract | ||
|---|---|---|
In this note, we show that three graph properties - strong connectivity, acyclicity, and reachability from a vertex $s$ to all vertices - each require a working memory of $\Omega (\epsilon m)$ on a graph with $m$ edges to be determined correctly with probability greater than $(1+\epsilon)/2$. |
Year | Venue | Field |
|---|---|---|
2014 | CoRR | Graph,Discrete mathematics,Combinatorics,Graph property,Vertex (geometry),Streaming algorithm,Reachability,Omega,Digraph,Mathematics |
DocType | Volume | Citations |
Journal | abs/1404.1323 | 1 |
PageRank | References | Authors |
0.35 | 5 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Glencora Borradaile | 1 | 275 | 21.24 |
| Claire Mathieu | 2 | 452 | 25.78 |
| Theresa Migler | 3 | 1 | 2.04 |