Sparse certificates for 2-connectivity in directed graphs
DOI10.1016/J.TCS.2017.06.015zbMATH Open1380.05185OpenAlexW2683784293MaRDI QIDQ1676306FDOQ1676306
Authors: Loukas Georgiadis, Giuseppe F. Italiano, Aikaterini Karanasiou, Charis Papadopoulos, Nikos Parotsidis 
Publication date: 6 November 2017
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2017.06.015
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
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)
Cites Work
- Network flows. Theory, algorithms, and applications.
- Maximal Flow Through a Network
- Title not available (Why is that?)
- Depth-First Search and Linear Graph Algorithms
- A linear time \(\frac{5}{3}\)-approximation for the minimum strongly-connected spanning subgraph problem
- Approximating the minimum strongly connected subgraph via a matching lower bound
- Approximating the smallest 2-vertex connected spanning subgraph of a directed graph
- Linear-Time Algorithms for Dominators and Other Path-Evaluation Problems
- 2-vertex connectivity in directed graphs
- Finding 2-edge and 2-vertex strongly connected components in quadratic time
- Algorithmic Aspects of Graph Connectivity
- Dominators in Linear Time
- Finding strong bridges and strong articulation points in linear time
- Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching
- 2-Edge Connectivity in Directed Graphs
- 2-connectivity in directed graphs: an experimental study
- Computing the 2-blocks of directed graphs
- A linear-time algorithm for a special case of disjoint set union
- Edge-disjoint spanning trees and depth-first search
- Title not available (Why is that?)
- A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
- Approximating the Minimum Equivalent Digraph
- Approximating the smallest \(k\)-edge connected spanning subgraph by LP-rounding
- Strong connectivity in directed graphs under failures, with applications
- On strongly connected digraphs with bounded cycle length
- A rounding by sampling approach to the minimum size \(k\)-arc connected subgraph problem
- Faster algorithms for computing maximal 2-connected subgraphs in sparse directed graphs
- Dominator tree certification and divergent spanning trees
- Approximating the smallest spanning subgraph for 2-edge-connectivity in directed graphs
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 spanning subgraph for 2-edge-connectivity in directed graphs
- Approximating the smallest 2-vertex connected spanning subgraph of a directed graph
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)
