Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2409.19773 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914960196501504 |
|---|---|
| author | Jaberi, Raed Mansour, Reham |
| author_facet | Jaberi, Raed Mansour, Reham |
| contents | Let $G=(V,E)$ be a strongly connected graph with $|V|\geq 3$. For $T\subseteq V$, the strongly connected graph $G$ is $2$-T-connected if $G$ is $2$-edge-connected and for each vertex $w$ in $T$, $w$ is not a strong articulation point. This concept generalizes the concept of $2$-vertex connectivity when $T$ contains all the vertices in $G$. This concept also generalizes the concept of $2$-edge connectivity when $|T|=0$. The concept of $2$-T-connectivity was introduced by Durand de Gevigney and Szigeti in $2018$. In this paper, we prove that there is a polynomial-time 4-approximation algorithm for the following problem: given a $2$-T-connected graph $G=(V,E)$, identify a subset $E^ {2T} \subseteq E$ of minimum cardinality such that $(V,E^{2T})$ is $2$-T-connected. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_19773 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The problem of computing a $2$-T-connected spanning subgraph with minimum number of edges in directed graphs Jaberi, Raed Mansour, Reham Data Structures and Algorithms Let $G=(V,E)$ be a strongly connected graph with $|V|\geq 3$. For $T\subseteq V$, the strongly connected graph $G$ is $2$-T-connected if $G$ is $2$-edge-connected and for each vertex $w$ in $T$, $w$ is not a strong articulation point. This concept generalizes the concept of $2$-vertex connectivity when $T$ contains all the vertices in $G$. This concept also generalizes the concept of $2$-edge connectivity when $|T|=0$. The concept of $2$-T-connectivity was introduced by Durand de Gevigney and Szigeti in $2018$. In this paper, we prove that there is a polynomial-time 4-approximation algorithm for the following problem: given a $2$-T-connected graph $G=(V,E)$, identify a subset $E^ {2T} \subseteq E$ of minimum cardinality such that $(V,E^{2T})$ is $2$-T-connected. |
| title | The problem of computing a $2$-T-connected spanning subgraph with minimum number of edges in directed graphs |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2409.19773 |