Computing $2$-twinless blocks

Abstract

Let $G=(V,E))$ be a directed graph. A $2$-twinless block in $G$ is a maximal vertex set $B\subseteq V$ of size at least $2$ such that for each pair of distinct vertices $x,y\in B$, and for each vertex $w\in V\setminus \left\{x,y\right\}$, the vertices $x,y$ are in the same twinless strongly connected component of $G\setminus \left\{w\right\}$. In this paper we present algorithms for computing the $2$-twinless blocks of a directed graph.

References in corpus (2)

• Finding 2-Edge and 2-Vertex Strongly Connected Components in Quadratic Time
• Linear-Time Algorithms for Computing Twinless Strong Articulation Points and Related Problems

Cited by in corpus (3)

• $2$-edge-twinless blocks
• Minimum $2$-vertex-twinless connected spanning subgraph problem
• Minimum $2$-vertex strongly biconnected spanning directed subgraph problem