Finding 2-Edge and 2-Vertex Strongly Connected Components in Quadratic Time
From MaRDI portal
Publication:3448829
DOI10.1007/978-3-662-47672-7_58zbMath1410.05203arXiv1412.6466OpenAlexW1697536320MaRDI QIDQ3448829
Sebastian Krinninger, Veronika Loitzenbauer, Monika R. Henzinger
Publication date: 27 October 2015
Published in: Automata, Languages, and Programming (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1412.6466
Analysis of algorithms (68W40) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40)
Related Items (13)
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 ⋮ Computing Critical Nodes in Directed Graphs ⋮ 2-edge-twinless blocks ⋮ Sparse certificates for 2-connectivity in directed graphs ⋮ Strong Connectivity in Directed Graphs under Failures, with Applications ⋮ On 2-strong connectivity orientations of mixed graphs and related problems ⋮ Unnamed Item ⋮ Finding densest \(k\)-connected subgraphs ⋮ Dynamic Dominators and Low-High Orders in DAGs ⋮ Computing 2-twinless blocks
Cites Work
- Unnamed Item
- Unnamed Item
- On computing the 2-vertex-connected components of directed graphs
- Finding strong bridges and strong articulation points in linear time
- 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
- Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology
- A matroid approach to finding edge connectivity and packing arborescences
- Efficient and Dynamic Algorithms for Alternating Büchi Games and Maximal End-Component Decomposition
- Linear-Time Algorithms for Dominators and Other Path-Evaluation Problems
- 2-Vertex Connectivity in Directed Graphs
- Using expander graphs to find vertex connectivity
- Algorithmic Aspects of Graph Connectivity
- Testing 2-Vertex Connectivity and Computing Pairs of Vertex-Disjoint s-t Paths in Digraphs
- An algorithm for finding all thek-components of a digraph
- Finding the Vertex Connectivity of Graphs
- An Algorithm for Determining Whether the Connectivity of a Graph is at Leastk
- Improved Algorithms for One-Pair and k-Pair Streett Objectives
- Dividing a Graph into Triconnected Components
- Computing Vertex Connectivity: New Bounds from Old Techniques
- Computer Science Logic
- 2-Edge Connectivity in Directed Graphs
- Digraphs
- Depth-First Search and Linear Graph Algorithms
- Networks
This page was built for publication: Finding 2-Edge and 2-Vertex Strongly Connected Components in Quadratic Time
