Approximating the smallest 2-vertex connected spanning subgraph of a directed graph
The paper considers the problem of approximating the smallest 2-vertex-connected spanning subgraph (2VCSS) of a 2-vertex-connected directed graph. A strongly connected digraph \(G\) is 2-vertex-connected if it has at least three vertices and no strong articulation points, i.e. there is no vertex \(x\) s.t. \(G \backslash x\) is not strongly connected. The previous best approximation ratio for this problem is 3/2, achieved by the algorithm by \textit{J. Cheriyan} and \textit{R. Thurimella} [SIAM J. Comput. 30, No. 2, 528--560 (2000; Zbl 1049.90104)], running in \(O(m^2)\) time. The first contribution of the paper are two linear-time algorithms that attain 3- and 2-approximate solutions, based on linear-time tests for 2-vertex-connectivity in digraphs. The 3-approximation algorithm also uses the concept of divergent spanning trees and the 2-approximation algorithm refines this approach by utilizing low-high orders. The second contribution is a new algorithm which is the result of a combination of two linear-time algorithms with the algorithm of Cheriyan and Thurimella in order to obtain a 3/2-approximation in faster \(O(m\sqrt n +n^2)\) time. A thorough experimental evaluation of all the above algorithms was conducted by the authors on a variety of input graphs. Their experimental results show the new 3/2-approximation algorithms kept essentially the same approximation ratio as the algorithm of Cheriyan and Thurimella, but it was significantly faster.
- Approximating the smallest 2-vertex connected spanning subgraph of a directed graph
- Approximating the smallest 2-vertex-connected spanning subgraph via low-high orders
- On computing the 2-vertex-connected components of directed graphs
- Two-connected spanning subgraphs with at most \(\frac{10}{7}{\mathrm{OPT}}\) edges
- Sparse certificates for 2-connectivity in directed graphs
- Approximating the smallest spanning subgraph for 2-edge-connectivity in directed graphs
- Finding 2-edge connected spanning subgraphs.
- Approximating the minimum strongly connected subgraph via a matching lower bound
- scientific article; zbMATH DE number 437534
- A data structure for dynamic trees
- A fast algorithm for finding dominators in a flowgraph
- A linear time \(\frac{5}{3}\)-approximation for the minimum strongly-connected spanning subgraph problem
- A new approach to the maximum-flow problem
- Addendum to “Dominator Tree Certification and Divergent Spanning Trees”
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching
- Approximating the Minimum Equivalent Digraph
- Approximating the smallest spanning subgraph for 2-edge-connectivity in directed graphs
- Computing 2-connected components and maximal 2-connected subgraphs in directed graphs: an experimental study
- Depth-First Search and Linear Graph Algorithms
- Dominator tree certification and divergent spanning trees
- Dominators in Linear Time
- Faster algorithms for computing maximal 2-connected subgraphs in sparse directed graphs
- Faster scaling algorithms for general graph matching problems
- Fault tolerant reachability for directed graphs
- Fault tolerant subgraph for single source reachability: generic and optimal
- Finding Dominators in Practice
- Finding strong bridges and strong articulation points in linear time
- scientific article; zbMATH DE number 437534 (Why is no real title available?)
- scientific article; zbMATH DE number 5485526 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- Linear time algorithms for two disjoint paths problems on directed acyclic graphs
- Linear-Time Algorithms for Dominators and Other Path-Evaluation Problems
- Mechanized verification of computing dominators for formalizing compilers
- Minimal n-fach zusammenhängende Digraphen. (Minimally n-connected digraphs)
- Network flows. Theory, algorithms, and applications.
- Testing 2-vertex connectivity and computing pairs of vertex-disjoint \(s\)-\(t\) paths in digraphs
- Sparse certificates for 2-connectivity in directed graphs
- Approximating the smallest 2-vertex connected spanning subgraph of a directed graph
- Approximating the smallest spanning subgraph for 2-edge-connectivity in directed graphs
- Approximating the smallest 2-vertex-connected spanning subgraph via low-high orders
- Minimum 2-vertex strongly biconnected spanning directed subgraph problem
This page was built for publication: Approximating the smallest 2-vertex connected spanning subgraph of a directed graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2286744)
