pith. sign in

arxiv: 2606.16087 · v2 · pith:EFHGO47Cnew · submitted 2026-06-15 · 💻 cs.DS

Problems related to strong connectivity and strong biconnectivity

classification 💻 cs.DS
keywords betastrongstronglysubgraphbiconnectedconnectedlbraceproblem
0
0 comments X
read the original 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.