Twinless articulation points and some related problems

2019/12/26 by Jaberi, Raed
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1912.11799

Abstract

Let G=(V,E) be a twinless strongly connected graph. a vertex v∈ V is a twinless articulation point if the subrgraph obtained from G by removing the vertex v is not twinless strongly connected. An edge e∈ E is a twinless bridge if the subgraph obtained from G by deleting e is not twiless strongly connected graph. In this paper we study twinless articulation points and twinless bridges. We also study the problem of finding a minimum cardinality edge subset E₁ ⊆ E such that the subgraph (V,E₁) is twinless strongly connected. Moreover, we present an algorithm for computing the 2-vertex-twinless connected components of G.

Related

• Linear-Time Algorithms for Computing Twinless Strong Articulation Points and Related Problems
• Minimum 2-vertex-twinless connected spanning subgraph problem
• b-articulation points and b-bridges in strongly biconnected directed graphs
• Computing all s-t bridges and articulation points simplified
• Identifying a 3-vertex strongly biconnected directed subgraph with minimum number of edges