Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Andrea Lincoln:

TR21-157 | 2nd November 2021
Monika Henzinger, Andrea Lincoln, Barna Saha

The Complexity of Average-Case Dynamic Subgraph Counting

Statistics of small subgraph counts such as triangles, four-cycles, and $s$-$t$ paths of short lengths reveal important structural properties of the underlying graph. These problems have been widely studied in social network analysis. In most relevant applications, the graphs are not only massive but also change dynamically over time. Most ... more >>>

ISSN 1433-8092 | Imprint