Computing the 3-edge-connected components of directed graphs in linear time
Georgiadis L, Italiano GF, Kosinas E. 2024. Computing the 3-edge-connected components of directed graphs in linear time. 65th Annual Symposium on Foundations of Computer Science. FOCS: Symposium on Foundations of Computer Science, 62–85.
Download
No fulltext has been uploaded. References only!
Conference Paper
| Published
| English
Scopus indexed
Author
Georgiadis, Loukas;
Italiano, Giuseppe F.;
Kosinas, EvangelosISTA
Corresponding author has ISTA affiliation
Department
Abstract
Let G be a directed graph with m edges and n vertices. We present a deterministic linear-time algorithm for computing the 3-edge-connected components of G. This is a significant improvement over the previous best bound by Georgiadis et al. [SODA 2023], which is Õ(m√{m}) and randomized. Our result is based on a novel characterization of 2-edge cuts in directed graphs and on a new technique that exploits the concept of divergent spanning trees and 2-connectivity-light graphs, and requires a careful modification of the minset-poset technique of Gabow [TALG 2016]. As a side result, our new technique yields also an oracle for providing in constant time a minimum edge-cut for any two vertices that are not 3-edge-connected. The oracle uses space O(n) and can be built in O(mlog n) time: given two query vertices, it determines in constant time whether they are 3-edge-connected, or provides a k-edge cut, with k≤ 2, that separates them.
Publishing Year
Date Published
2024-10-01
Proceedings Title
65th Annual Symposium on Foundations of Computer Science
Publisher
IEEE
Acknowledgement
Giuseppe F. Italiano was partially supported by the Italian Ministry of
University and Reseach under PRIN Project n. 2022TS4Y3N - EXPAND: scalable algorithms for EXPloratory Analyses of heterogeneous and dynamic Networked Data.
Page
62-85
Conference
FOCS: Symposium on Foundations of Computer Science
Conference Location
Chicago, IL, United States
Conference Date
2024-10-27 – 2024-10-30
ISBN
IST-REx-ID
Cite this
Georgiadis L, Italiano GF, Kosinas E. Computing the 3-edge-connected components of directed graphs in linear time. In: 65th Annual Symposium on Foundations of Computer Science. IEEE; 2024:62-85. doi:10.1109/focs61266.2024.00015
Georgiadis, L., Italiano, G. F., & Kosinas, E. (2024). Computing the 3-edge-connected components of directed graphs in linear time. In 65th Annual Symposium on Foundations of Computer Science (pp. 62–85). Chicago, IL, United States: IEEE. https://doi.org/10.1109/focs61266.2024.00015
Georgiadis, Loukas, Giuseppe F. Italiano, and Evangelos Kosinas. “Computing the 3-Edge-Connected Components of Directed Graphs in Linear Time.” In 65th Annual Symposium on Foundations of Computer Science, 62–85. IEEE, 2024. https://doi.org/10.1109/focs61266.2024.00015.
L. Georgiadis, G. F. Italiano, and E. Kosinas, “Computing the 3-edge-connected components of directed graphs in linear time,” in 65th Annual Symposium on Foundations of Computer Science, Chicago, IL, United States, 2024, pp. 62–85.
Georgiadis L, Italiano GF, Kosinas E. 2024. Computing the 3-edge-connected components of directed graphs in linear time. 65th Annual Symposium on Foundations of Computer Science. FOCS: Symposium on Foundations of Computer Science, 62–85.
Georgiadis, Loukas, et al. “Computing the 3-Edge-Connected Components of Directed Graphs in Linear Time.” 65th Annual Symposium on Foundations of Computer Science, IEEE, 2024, pp. 62–85, doi:10.1109/focs61266.2024.00015.