Faster algorithms for computing maximal 2-connected subgraphs in sparse directed graphs

DOI10.1137/1.9781611974782.124MaRDI QIDQ4575870zbMATH OpenOpenAlexFDO

Authors Shiri Chechik, Thomas Dueholm Hansen, Giuseppe F. Italiano, Veronika Loitzenbauer, Nikos Parotsidis

Publication date 16 July 2018

Published in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1705.10709

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Connectivity (05C40)

Abstract: 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(n^2)$ time algorithms for the directed case, thus improving the running times for dense graphs. Our new algorithms run in time $O(m^{3/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(m^{3/2}logn)$, improving again for sparse graphs the best known algorithm by Henzinger et al. [ICALP 2015] that runs in $O(n^{2}logn)$ time.

Recommendations

• Finding 2-edge and 2-vertex strongly connected components in quadratic time
• Computing 2-connected components and maximal 2-connected subgraphs in directed graphs: an experimental study
• 2-Connectivity in Directed Graphs (Invited Talk)
• 2-edge connectivity in directed graphs
• Sparse certificates for 2-connectivity in directed graphs

Cited in

(13)

• scientific article; zbMATH DE number 7765396 (Why is no real title available?)
• Computing the 2-blocks of directed graphs
• On finding sparse three-edge-connected and three-vertex-connected spanning subgraphs
• Finding 2-edge and 2-vertex strongly connected components in quadratic time
• Computing 2-connected components and maximal 2-connected subgraphs in directed graphs: an experimental study
• Computing Minimal Spanning Subgraphs in Linear Time
• Sparse certificates for 2-connectivity in directed graphs
• Strong connectivity in directed graphs under failures, with applications
• Finding the edge connectivity of directed graphs
• Approximating the smallest 2-vertex connected spanning subgraph of a directed graph
• Improved approximation algorithms for MAX \(\frac{n}2\)-DIRECTED-BISECTION and MAX \(\frac{n}2\)-DENSE-SUBGRAPH
• Contracting a planar graph efficiently
• Finding densest \(k\)-connected subgraphs

This page was built for publication: Faster algorithms for computing maximal 2-connected subgraphs in sparse directed graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575870)