论文标题
至少$ 2 $ -VERTEX强烈双重跨越指导子图问题
Minimum $2$-vertex strongly biconnected spanning directed subgraph problem
论文作者
论文摘要
如果$ g $连接$ g $，并且其基础图是双连接的，则有点$ g =（v，e）$是强烈的。如果$ | v | \ geq 3 $，$ g =（v，e）$强烈的指向图$ g =（v，e）$被称为$ 2 $ vertex-tronglonglongy biconnected，则在$ v \ setminus \ setMinus \ left \ lbrace w \ lbrace w \ rbrace $ rbrace $ rbrace $上是强烈的biconnnnnnection的v \ setminus \ left \ lbrace w \ rbrace $ biconnection verte $ w \ w \ w \。在本文中，我们研究以下问题。 Given a $2$-vertex-strongly biconnected directed graph $G=(V,E)$, compute an edge subset $E^{2sb} \subseteq E$ of minimum size such that the subgraph $(V,E^{2sb})$ is $2$-vertex-strongly biconnected.
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|\geq 3$ and the induced subgraph on $V\setminus\left\lbrace w\right\rbrace $ is strongly biconnected for every vertex $w\in 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} \subseteq E$ of minimum size such that the subgraph $(V,E^{2sb})$ is $2$-vertex-strongly biconnected.
