Strong Connectivity in Directed Graphs under Failures, with Applications
From MaRDI portal
Publication:5123984
DOI10.1137/19M1258530zbMath1448.05116OpenAlexW3082938733MaRDI QIDQ5123984
Nikos Parotsidis, Loukas Georgiadis, Giuseppe F. Italiano
Publication date: 17 September 2020
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/19m1258530
Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Identifying sets of key players in a social network
- Finding dominators via disjoint set union
- Finding strong bridges and strong articulation points in linear time
- An efficient strongly connected components algorithm in the fault tolerant model
- Detecting critical nodes in sparse graphs
- Maintaining bridge-connected and biconnected components on-line
- Edge-disjoint spanning trees and depth-first search
- 2-vertex connectivity in directed graphs
- Sparse certificates for 2-connectivity in directed graphs
- The critical node detection problem in networks: a survey
- Incremental strong connectivity and 2-connectivity in directed graphs
- Fast Algorithms for Finding Nearest Common Ancestors
- Linear-Time Algorithms for Dominators and Other Path-Evaluation Problems
- Finding 2-Edge and 2-Vertex Strongly Connected Components in Quadratic Time
- Oracles for Distances Avoiding a Failed Node or Link
- An algorithm for finding all thek-components of a digraph
- A fast algorithm for finding dominators in a flowgraph
- Bijoin points, bibridges, and biblocks of directed graphs
- Finding Dominators in Directed Graphs
- Efficiency of a Good But Not Linear Set Union Algorithm
- Dominators in Linear Time
- Computing Critical Nodes in Directed Graphs
- Faster Algorithms for Computing Maximal 2-Connected Subgraphs in Sparse Directed Graphs
- Incremental 2-Edge-Connectivity in Directed Graphs
- Counterexamples for Directed and Node Capacitated Cut-Trees
- Dominator Tree Certification and Divergent Spanning Trees
- 2-Edge Connectivity in Directed Graphs
- An Optimal O ( nm ) Algorithm for Enumerating All Walks Common to All Closed Edge-covering Walks of a Graph
- Prime Factorization of the Kirchhoff Polynomial: Compact Enumeration of Arborescences
- 2-Connectivity in Directed Graphs: An Experimental Study
- Computing 2-Connected Components and Maximal 2-Connected Subgraphs in Directed Graphs: An Experimental Study
- Computing the 2-blocks of directed graphs
- Depth-First Search and Linear Graph Algorithms
- A fully dynamic algorithm for maintaining the transitive closure
This page was built for publication: Strong Connectivity in Directed Graphs under Failures, with Applications
