Abstract:Let $G=(V,E)$ be a strong biconnected graph and let $B \subseteq V$ such that for each vertex $w \in B$, the subgraph $G \setminus \lbrace w\rbrace$ is strongly connected. In this paper we study the problem of computing a subset $E_{\beta} \subseteq E$ of minimum size such that the subgraph $G_{\beta}=(V,E_{\beta})$ is strongly biconnected and for each vertex $w \in B$, the subgraph $G_{\beta} \setminus \lbrace w\rbrace$ is strongly connected. We prove that there exists a polynomial time $7$-approximation algorithm for this problem.
From: R Jaberi [view email]
[v1]
Mon, 15 Jun 2026 00:56:38 UTC (10 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。