Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with dynamic:
TR95-020 | 8th March 1995
William Hurwood

Dynamic Fault Diagnosis

We consider a dynamic fault diagnosis problem: There are n
processors, to be tested in a series of rounds. In every
testing round we use a directed matching to have some
processors report on the status (good or faulty) of other
processors. Also in each round ... more >>>

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