2014/09/22 by Loukas Georgiadis, Georgiadis, Loukas, Giuseppe F. Italiano +5
Computer Science · #Advanced Graph Theory Research #Data Structures and Algorithms (cs.DS) #Distributed systems and fault tolerance #FOS: Computer and information sciences #Interconnection Networks and Systems #cs.DS
paper · pdf · doi:10.48550/arxiv.1409.6277
arXiv admin note: substantial text overlap with arXiv:1407.3041
openalex publication_date 2014/09/22 · arxiv created 2015/02/19 · arxiv updated 2015/02/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We complement our study of 2-connectivity in directed graphs, by considering the computation of the following 2-vertex-connectivity relations: We say that two vertices v and w are 2-vertex-connected if there are two internally vertex-disjoint paths from v to w and two internally vertex-disjoint paths from w to v. We also say that v and w are vertex-resilient if the removal of any vertex different from v and w leaves v and w in the same strongly connected component. We show how to compute the above relations in linear time so that we can report in constant time if two vertices are 2-vertex-connected or if they are vertex-resilient. We also show how to compute in linear time a sparse certificate for these relations, i.e., a subgraph of the input graph that has O(n) edges and maintains the same 2-vertex-connectivity and vertex-resilience relations as the input graph, where n is the number of vertices.