Computing the (k+2)-Edge-Connected Components in k-Edge-Connected Digraphs in Subquadratic Time

Loukas Georgiadis, Evangelos Kipouridis, Evangelos Kosinas +2

Computing edge-connected components in directed and undirected graphs is a fundamental and well-studied problem in graph algorithms. In a very recent breakthrough, Korhonen [STOC 2…