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.
Computing the 4-edge-connected components of a graph in linear time / Georgiadis, Loukas; Italiano, Giuseppe Francesco; Kosinas, E.. - 204:(2021), pp. 1-17. [10.4230/LIPIcs.ESA.2021.47]
Computing the 4-edge-connected components of a graph in linear time
Georgiadis L.;Italiano G. F.;
2021
Abstract
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.
| File | Dimensione | Formato | |
|---|---|---|---|
|
LIPIcs-ESA-2021-47.pdf
Open Access
Tipologia:
Versione dell'editore
Licenza:
Tutti i diritti riservati
Dimensione
810.91 kB
Formato
Adobe PDF
|
810.91 kB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
