39 citations · 55 across the 5 of their papers we have counts for
4 papers · 1 filter
Random walks and forbidden minors III: poly(d/ε)-time partition oracles for minor-free graph classes
Akash Kumar, C. Seshadhri, Andrew Stolman
Consider the family of bounded degree graphs in any minor-closed family (such as planar graphs). Let d be the degree bound and n be the number of vertices of such a graph. Graphs i…
How to Count Triangles, without Seeing the Whole Graph
Suman K. Bera, C. Seshadhri
Triangle counting is a fundamental problem in the analysis of large graphs. There is a rich body of work on this problem, in varying streaming and distributed models, yet all these…
How the Degeneracy Helps for Triangle Counting in Graph Streams
Suman K. Bera, C. Seshadhri
We revisit the well-studied problem of triangle count estimation in graph streams. Given a graph represented as a stream of edges, our aim is to compute a -a…
Linear Time Subgraph Counting, Graph Degeneracy, and the Chasm at Size Six
Suman K. Bera, Noujan Pashanasangi, C. Seshadhri
We consider the problem of counting all -vertex subgraphs in an input graph, for any constant . This problem (denoted sub-cnt) has been studied extensively in both theory…