2-edge connectivity in directed graphs

DOI10.1137/1.9781611973730.132MaRDI QIDQ5363073zbMATH OpenOpenAlexFDO

Authors Loukas Georgiadis, Giuseppe F. Italiano, Luigi Laura, Nikos Parotsidis

Publication date 5 October 2017

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

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

Mathematics Subject Classification ID

Connectivity (05C40) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Abstract: Edge and vertex connectivity are fundamental concepts in graph theory. While they have been thoroughly studied in the case of undirected graphs, surprisingly not much has been investigated for directed graphs. In this paper we study $2$-edge connectivity problems in directed graphs and, in particular, we consider the computation of the following natural relation: We say that two vertices $v$ and $w$ are $2$-edge-connected if there are two edge-disjoint paths from $v$ to $w$ and two edge-disjoint paths from $w$ to $v$. This relation partitions the vertices into blocks such that all vertices in the same block are $2$-edge-connected. Differently from the undirected case, those blocks do not correspond to the $2$-edge-connected components of the graph. We show how to compute this relation in linear time so that we can report in constant time if two vertices are $2$-edge-connected. We also show how to compute in linear time a sparse certificate for this relation, i.e., a subgraph of the input graph that has $O(n)$ edges and maintains the same $2$-edge-connected blocks as the input graph.

Recommendations

• 2-Edge Connectivity in Directed Graphs
• Finding 2-edge and 2-vertex strongly connected components in quadratic time
• 2-vertex connectivity in directed graphs
• 2-vertex connectivity in directed graphs
• 2-Connectivity in Directed Graphs (Invited Talk)

Cited in

(17)

• 2-vertex connectivity in directed graphs
• 2-edge-twinless blocks
• On computing the 2-vertex-connected components of directed graphs
• Efficient algorithm for computing all low s-t edge connectivities in directed graphs
• 2-vertex connectivity in directed graphs
• Finding 2-edge and 2-vertex strongly connected components in quadratic time
• Faster algorithms for computing maximal 2-connected subgraphs in sparse directed graphs
• 2-Connectivity in Directed Graphs (Invited Talk)
• 2-Edge Connectivity in Directed Graphs
• Minimum 2-vertex strongly biconnected spanning directed subgraph problem
• Dynamic Dominators and Low-High Orders in DAGs
• 2-connectivity in directed graphs: an experimental study
• Computing the 2-blocks of directed graphs
• Computing 2-twinless blocks
• On the (di)graphs with (directed) proper connection number two
• New extremal bounds for reachability and strong-connectivity preservers under failures
• New extremal bounds for reachability and strong-connectivity preservers under failures

This page was built for publication: 2-edge connectivity in directed graphs

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