Approximating the smallest 2-vertex connected spanning subgraph of a directed graph
DOI10.1016/j.tcs.2019.09.040zbMath1448.68355OpenAlexW1811642211WikidataQ127194840 ScholiaQ127194840MaRDI QIDQ2286744
Loukas Georgiadis, Giuseppe F. Italiano, Aikaterini Karanasiou
Publication date: 22 January 2020
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://hal.inria.fr/hal-02335015
directed graphsapproximation algorithmsvertex connectivity2-vertex-connected spanning subgraphsexperimental evaluation of algorithms
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Directed graphs (digraphs), tournaments (05C20)
Related Items (1)
Uses Software
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
- Minimal n-fach zusammenhängende Digraphen. (Minimally n-connected digraphs)
- Fault tolerant reachability for directed graphs
- A data structure for dynamic trees
- Linear time algorithms for two disjoint paths problems on directed acyclic graphs
- Linear-Time Algorithms for Dominators and Other Path-Evaluation Problems
- Approximating the Smallest Spanning Subgraph for 2-Edge-Connectivity in Directed Graphs
- Testing 2-Vertex Connectivity and Computing Pairs of Vertex-Disjoint s-t Paths in Digraphs
- A new approach to the maximum-flow problem
- A fast algorithm for finding dominators in a flowgraph
- Dominators in Linear Time
- Faster scaling algorithms for general graph matching problems
- Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching
- Faster Algorithms for Computing Maximal 2-Connected Subgraphs in Sparse Directed Graphs
- Approximating the Minimum Equivalent Digraph
- Mechanized Verification of Computing Dominators for Formalizing Compilers
- Dominator Tree Certification and Divergent Spanning Trees
- Addendum to “Dominator Tree Certification and Divergent Spanning Trees”
- Computing 2-Connected Components and Maximal 2-Connected Subgraphs in Directed Graphs: An Experimental Study
- Finding Dominators in Practice
- Fault tolerant subgraph for single source reachability: generic and optimal
- Depth-First Search and Linear Graph Algorithms
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
This page was built for publication: Approximating the smallest 2-vertex connected spanning subgraph of a directed graph
