Ferry Timmers: Maintaining strongly connected components efficiently, under edge deletions

Event Details

Assume we have a directed graph. We can find the strongly connected components in this graph using for instance Tarjan’s algorithm. Let’s say we remove an edge from the graph. Can we recalculate the SCCs? A (recent) paper by Bernstein, Probst et.al. presents a way tot do this efficiently. I’ll roughly discuss my experiences with the algorithm and then focus on ES-trees, a clever data structure the algorithm extended.