Definition
Strong bridge in strongly-connected directed graph: edge (u,v) such that after removal, graph no longer strongly connected.
Advertisement
Algorithm
Italiano et al: O(V+E) via dominator trees. Complex — dominator trees on both G and reverse G.
Advertisement
Dominators
u dominates v: every path from root to v passes through u. Computed in O((V+E)·α(V)) via Lengauer-Tarjan.
Applications
Directed graph robustness (route networks). Dependency analysis. Program flow (post-dominators used in compilers).