Wu and Grumbach introduced the concept of strongly biconnected directed graphs. A directed graph $G=(V,E)$ is called strongly biconnected if the directed graph $G$ is strongly connected and the underlying undirected graph of $G$ is biconnected. A strongly biconnected directed graph $G=(V,E)$ is said to be $2$-edge-strongly biconnected if it has at least three vertices and the directed subgraph $(V,E\setminus\left\lbrace e\right\rbrace )$ is strongly biconnected for all $e \in E$. Let $G=(V,E)$ be a $2$-edge-strongly biconnected directed graph. In this paper we study the problem of computing a minimum size subset $H \subseteq E$ such that the directed subgraph $(V,H)$ is $2$-edge-strongly biconnected.
翻译:Wu and Grumbach 引入了“紧密双连接的定向图形”的概念。如果直接的图形$G$(V,E)密切相连,且基本的非定向图形$G$是双连接的,则直接的图形$G=(V,E)被称为“强烈双连接的”。一个强烈双连接的定向图形$G=(V,E)据说是$G=(V,E),如果它至少有三个垂直和直接的子图$(V,E\setminus\left\lbrace e\right\rbrbrace)非常紧密的双连接。让(V,E)$G=(V,E)成为两链接的双链接的双链接的原始图形。在本文中,我们研究如何计算最小尺寸的$H subseteqeet E$(eq)的问题,因此,直接的子图$(V,H)是2美元。