Name
Abstract | ||
|---|---|---|
We consider the updatable streaming graph model, where edges of a graph arrive or depart in arbitrary sequence and are processed in an online fashion using sub-linear space and time. We study the problem of estimating aggregate path metrics Pk defined as the number of pairs of vertices that have a simple path between them of length k. For a streaming undirected graph with n vertices, m edges and r components, we present an $\tilde{O}(m(m-r)^{-1/4})$ space algorithm for estimating P2 and an $\Omega(\sqrt{m})$ space lower bound. We show that estimating P2 over directed streaming graphs, and estimating Pk over streaming graphs (whether directed or undirected), for any k ≥3 requires Ω(n2) space. We also present a space lower bound of Ω(n2) for the problems of (a) deterministically testing the connectivity, and, (b) estimating the size of transitive closure, of undirected streaming graphs that allow both edge-insertions and deletions. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1007/11940128_18 | ISAAC |
Keywords | Field | DocType |
aggregate path metrics,n vertex,graph model,arbitrary sequence,undirected graph,sub-linear space,space algorithm,m edge,path aggregate,simple path,length k,transitive closure,linear space,lower bound | Adjacency list,Graph theory,Discrete mathematics,Combinatorics,Path (graph theory),Vertex (geometry),Linear space,Directed graph,Connectivity,Longest path problem,Mathematics | Conference |
Volume | ISSN | ISBN |
4288 | 0302-9743 | 3-540-49694-7 |
Citations | PageRank | References |
5 | 0.50 | 8 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sumit Ganguly | 1 | 813 | 236.01 |
| Barna Saha | 2 | 626 | 37.56 |