论文标题
至少$ 2 $ - vertex-twinless连接跨越子图问题
Minimum $2$-vertex-twinless connected spanning subgraph problem
论文作者
论文摘要
给定$ 2 $ - vertex-twinless连接的有向图$ g =（v，e）$，至少$ 2 $ 2 $ - vertex-twinless-twinless连接的跨越子段问题是找到一个最小的基数边缘子集$ e^{t} \ subseteq e $，以便该子$（v，e^，e^，e^t} $ 2 $ 2 $ 2 $ 2 $ - 令$ g^{1} $为$ g $的最小$ 2 $ 2 $ -VERTEX连接子图。在本文中，我们介绍了$（2+a_ {t}/2）$ - 最低$ 2 $ -2 $ - vertex-twinless-twinless twinless connected跨越子段问题的近似算法，其中$ a_ {t} $是$ g^{1} $中的无二个无双重关节点的数量。
Given a $2$-vertex-twinless connected directed graph $G=(V,E)$, the minimum $2$-vertex-twinless connected spanning subgraph problem is to find a minimum cardinality edge subset $E^{t} \subseteq E$ such that the subgraph $(V,E^{t})$ is $2$-vertex-twinless connected. Let $G^{1}$ be a minimal $2$-vertex-connected subgraph of $G$. In this paper we present a $(2+a_{t}/2)$-approximation algorithm for the minimum $2$-vertex-twinless connected spanning subgraph problem, where $a_{t}$ is the number of twinless articulation points in $G^{1}$.
