Graph Connectivity and Falling Sand Problems
Dynamic Graph Connectivity When adding a new edge between two nodes in a graph, all bridge edges along the path between those nodes become non-bridge edges. This observation leads to efficient updates using tree decomposition techniques or more straightforward approaches like edge contraction. The f...