2017/05/30 by Shiri Chechik, Thomas Dueholm Hansen, Chechik, Shiri +7
Computer Science · #Caching and Content Delivery #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.1705.10709
openalex publication_date 2017/05/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Connectivity related concepts are of fundamental interest in graph theory. The area has received extensive attention over four decades, but many problems remain unsolved, especially for directed graphs. A directed graph is 2-edge-connected (resp., 2-vertex-connected) if the removal of any edge (resp., vertex) leaves the graph strongly connected. In this paper we present improved algorithms for computing the maximal 2-edge- and 2-vertex-connected subgraphs of a given directed graph. These problems were first studied more than 35 years ago, with \widetildeO(mn) time algorithms for graphs with m edges and n vertices being known since the late 1980s. In contrast, the same problems for undirected graphs are known to be solvable in linear time. Henzinger et al. [ICALP 2015] recently introduced O(n2) time algorithms for the directed case, thus improving the running times for dense graphs. Our new algorithms run in time O(m3/2), which further improves the running times for sparse graphs. The notion of 2-connectivity naturally generalizes to k-connectivity for k>2. For constant values of k, we extend one of our algorithms to compute the maximal k-edge-connected in time O(m3/2 logn), improving again for sparse graphs the best known algorithm by Henzinger et al. [ICALP 2015] that runs in O(n2 log n) time.