55 citations · 116 across the 11 of their papers we have counts for
12 papers
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…
Provable and practical approximations for the degree distribution using sublinear graph samples
Talya Eden, Shweta Jain, Ali Pinar +2
The degree distribution is one of the most fundamental properties used in the analysis of massive graphs. There is a large literature on graph sampling, where the goal is to estima…
Local Algorithms for Hierarchical Dense Subgraph Discovery
Ahmet Erdem Sariyuce, C. Seshadhri, Ali Pinar
Finding the dense regions of a graph and relations among them is a fundamental problem in network analysis. Core and truss decompositions reveal dense subgraphs with hierarchical r…