Sparse certificates for 2-connectivity in directed graphs
From MaRDI portal
Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Flows in graphs (05C21) Connectivity (05C40)
Recommendations
- Approximating the smallest spanning subgraph for 2-edge-connectivity in directed graphs
- Faster algorithms for computing maximal 2-connected subgraphs in sparse directed graphs
- Approximating the smallest 2-vertex connected spanning subgraph of a directed graph
- Approximating the smallest 2-vertex connected spanning subgraph of a directed graph
- 2-Edge Connectivity in Directed Graphs
Cites work
- scientific article; zbMATH DE number 5485526 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- 2-Edge Connectivity in Directed Graphs
- 2-connectivity in directed graphs: an experimental study
- 2-vertex connectivity in directed graphs
- A linear time \(\frac{5}{3}\)-approximation for the minimum strongly-connected spanning subgraph problem
- A linear-time algorithm for a special case of disjoint set union
- A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
- A rounding by sampling approach to the minimum size \(k\)-arc connected subgraph problem
- Algorithmic Aspects of Graph Connectivity
- Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching
- Approximating the Minimum Equivalent Digraph
- Approximating the minimum strongly connected subgraph via a matching lower bound
- Approximating the smallest 2-vertex connected spanning subgraph of a directed graph
- Approximating the smallest \(k\)-edge connected spanning subgraph by LP-rounding
- Approximating the smallest spanning subgraph for 2-edge-connectivity in directed graphs
- Computing the 2-blocks of directed graphs
- Depth-First Search and Linear Graph Algorithms
- Dominator tree certification and divergent spanning trees
- Dominators in Linear Time
- Edge-disjoint spanning trees and depth-first search
- Faster algorithms for computing maximal 2-connected subgraphs in sparse directed graphs
- Finding 2-edge and 2-vertex strongly connected components in quadratic time
- Finding strong bridges and strong articulation points in linear time
- Linear-Time Algorithms for Dominators and Other Path-Evaluation Problems
- Maximal Flow Through a Network
- Network flows. Theory, algorithms, and applications.
- On strongly connected digraphs with bounded cycle length
- Strong connectivity in directed graphs under failures, with applications
Cited in
(6)- Faster algorithms for computing maximal 2-connected subgraphs in sparse directed graphs
- Sparse certificates and removable cycles in \(l\)-mixed \(p\)-connected graphs
- Approximating the smallest 2-vertex-connected spanning subgraph via low-high orders
- Strong connectivity in directed graphs under failures, with applications
- Approximating the smallest 2-vertex connected spanning subgraph of a directed graph
- Approximating the smallest spanning subgraph for 2-edge-connectivity in directed graphs
This page was built for publication: Sparse certificates for 2-connectivity in directed graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1676306)
