Computing the 2-blocks of directed graphs

DOI10.1051/ita/2015001zbMath1342.05055arXiv1407.6178OpenAlexW2964014743MaRDI QIDQ5501861

Raed Jaberi

Publication date: 14 August 2015

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

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

zbMATH Keywords

graph algorithmapproximation algorithmdirected graph2-blockstrong articulation pointstrong bridge

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40)

Related Items (9)

On computing the 2-vertex-connected components of directed graphs ⋮ 2-Vertex Connectivity in Directed Graphs ⋮ Approximating the Smallest Spanning Subgraph for 2-Edge-Connectivity in Directed Graphs ⋮ 2-vertex connectivity in directed graphs ⋮ 2-edge-twinless blocks ⋮ Sparse certificates for 2-connectivity in directed graphs ⋮ Strong Connectivity in Directed Graphs under Failures, with Applications ⋮ Dynamic Dominators and Low-High Orders in DAGs ⋮ Computing 2-twinless blocks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding strong bridges and strong articulation points in linear time
• The complexity of finding two disjoint paths with min-max objective function
• A linear time \(\frac{5}{3}\)-approximation for the minimum strongly-connected spanning subgraph problem
• The directed subgraph homeomorphism problem
• Edge-disjoint spanning trees and depth-first search
• Dominators, Directed Bipolar Orders, and Independent Spanning Trees
• 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
• Testing 2-Vertex Connectivity and Computing Pairs of Vertex-Disjoint s-t Paths in Digraphs
• A fast algorithm for finding dominators in a flowgraph
• Approximation Algorithms for Several Graph Augmentation Problems
• Bijoin points, bibridges, and biblocks of directed graphs
• Dominators in Linear Time
• Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching
• Max flows in O(nm) time, or better
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• Depth-First Search and Linear Graph Algorithms
• A textbook of graph theory

This page was built for publication: Computing the 2-blocks of directed graphs