Approximating the Smallest Spanning Subgraph for 2-Edge-Connectivity in Directed Graphs

DOI10.1007/978-3-662-48350-3_49zbMath1466.68058arXiv1509.02841OpenAlexW1884703449WikidataQ61609309 ScholiaQ61609309MaRDI QIDQ3452820

Charis Papadopoulos, Loukas Georgiadis, Nikos Parotsidis, Giuseppe F. Italiano

Publication date: 19 November 2015

Published in: Algorithms - ESA 2015 (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1509.02841

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40)

Related Items

Sparse certificates for 2-connectivity in directed graphs, Approximating the smallest 2-vertex connected spanning subgraph of a directed graph

Cites Work

• 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
• Edge-disjoint spanning trees and depth-first search
• Approximating node connectivity problems via set covers
• 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
• 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
• Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching
• Computing the 2-blocks of directed graphs