论文标题
至少$ 2 $ - 边缘强烈双重跨越指导子图问题
Minimum $2$-edge strongly biconnected spanning directed subgraph problem
论文作者
论文摘要
WU和Grumbach介绍了强烈双连接的定向图的概念。如果指示图$ g $连接，并且$ g $的基本无向图是双连接的，则指示图$ g =（v，e）$被称为强烈双连接。如果它至少具有三个顶点，并且指向子graph $（v，e \ setMinus \ left \ lbrace e \ rbrace \ rbrace \ rbrace）$强烈地将$ biconnnne是强烈的。令$ g =（v，e）$为$ 2 $ - 边缘双连接的有向图。在本文中，我们研究了计算最小尺寸子集$ h \ subseteq e $的问题，以使指示子图$（v，h）$是$ 2 $ - 边缘强烈双重连接。
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.
