Checking if two nodes are connected in a graph (whether there's a path between them) is a very easy problem to solve if the graph is given to you in advance. But what if the graph can change by having edges added in dynamically? This problem requires a more clever solution, one that's trivial to code up but whose analysis is one of the most surprising of the quarter.
Readings
- Raimund Seidel and Micha and Sharir. Top-Down Analysis of Path Compression
Links