Minimum 2-vertex strongly biconnected spanning directed subgraph problem
share
A directed graph G=(V,E) is strongly biconnected if G is strongly connected and its underlying graph is biconnected. A strongly biconnected directed graph G=(V,E) is called 2-vertex-strongly biconnected if |V|≥ 3 and the induced subgraph on V∖{ w} is strongly biconnected for every vertex w∈ V. In this paper we study the following problem. Given a 2-vertex-strongly biconnected directed graph G=(V,E), compute an edge subset E^2sb⊆ E of minimum size such that the subgraph (V,E^2sb) is 2-vertex-strongly biconnected.
READ FULL TEXT