Sparse certificates for 2-connectivity in directed graphs
From MaRDI portal
Publication:1676306
DOI10.1016/j.tcs.2017.06.015zbMath1380.05185OpenAlexW2683784293MaRDI QIDQ1676306
Nikos Parotsidis, Loukas Georgiadis, Charis Papadopoulos, Aikaterini Karanasiou, Giuseppe F. Italiano
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
Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40) Flows in graphs (05C21)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Finding strong bridges and strong articulation points in linear time
- 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
- Edge-disjoint spanning trees and depth-first search
- On strongly connected digraphs with bounded cycle length
- A Rounding by Sampling Approach to the Minimum Size k-Arc Connected Subgraph Problem
- Approximating the smallest k -edge connected spanning subgraph by LP-rounding
- Approximating the Smallest 2-Vertex Connected Spanning Subgraph of a Directed Graph
- Maximal Flow Through a Network
- 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
- Approximating the Smallest Spanning Subgraph for 2-Edge-Connectivity in Directed Graphs
- Algorithmic Aspects of Graph Connectivity
- Dominators in Linear Time
- Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching
- Strong Connectivity in Directed Graphs under Failures, with Applications
- Faster Algorithms for Computing Maximal 2-Connected Subgraphs in Sparse Directed Graphs
- Approximating the Minimum Equivalent Digraph
- Dominator Tree Certification and Divergent Spanning Trees
- 2-Edge Connectivity in Directed Graphs
- 2-Connectivity in Directed Graphs: An Experimental Study
- Computing the 2-blocks of directed graphs
- Depth-First Search and Linear Graph Algorithms
