Topic List
Dynamic Graph Problems
In the general form, dynamic graph problems consists of a sequence of graph updates and queries. Unlike the streaming model, the queries are interleaving between the updates.
For the graph updates, there are three types of updates:
- Inserting an edge.
- Deleting an edge.
- Modifying an edge.
In most of the cases edge modification can be implemented by insertions and deletions. For the queries, it varies for the purpose of the problem.
There are several different models when we try to dynamize the graph. For example, if random coins are used, then whether adversaries can see those random coins or internal states of a data structure would effect the performance (correctness and time complexity) of the data structure.
Dynamic Connectivity
Query$(u, v)$: asking whether $u$ and $v\in V$ are connected.
We have Borůvka’s Hierarchy (suitable for worst-case monte-carlo data structures) and Henzinger-King-Thorup’s Hierarchy (suitable for amortized data structures).
$k$-edge connectivity
Query$(u, v)$: asking whether $u$ and $v\in V$ are $k$-edge-connected.
Minimum Spanning Trees
Query$()$: Find out the weight sum of the minimum spanning tree.