Georgiadis, Loukas
[VerfasserIn];
Italiano, Giuseppe F.
[VerfasserIn];
Kosinas, Evangelos
[VerfasserIn]
;
Loukas Georgiadis and Giuseppe F. Italiano and Evangelos Kosinas
[MitwirkendeR]
Computing the 4-Edge-Connected Components of a Graph in Linear Time
Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
We present the first linear-time algorithm that computes the 4-edge-connected components of an undirected graph. Hence, we also obtain the first linear-time algorithm for testing 4-edge connectivity. Our results are based on a linear-time algorithm that computes the 3-edge cuts of a 3-edge-connected graph G, and a linear-time procedure that, given the collection of all 3-edge cuts, partitions the vertices of G into the 4-edge-connected components.