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

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
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.

Export

Marked Publications

Open Data ISTA Research Explorer

Search this title in

Google Scholar
ISBN Search