Packing internally disjoint Steiner paths of data center networks
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913207483891712 |
|---|---|
| author | Zhu, Wen-Han Hao, Rong-Xia Chang, Jou-Ming Lee, Jaeun |
| author_facet | Zhu, Wen-Han Hao, Rong-Xia Chang, Jou-Ming Lee, Jaeun |
| contents | Let $S\subseteq V(G)$ and $π_{G}(S)$ denote the maximum number $t$ of edge-disjoint paths $P_{1},P_{2},\ldots,P_{t}$ in a graph $G$ such that $V(P_{i})\cap V(P_{j})=S$ for any $i,j\in\{1,2,\ldots,t\}$ and $i\neq j$. If $S=V(G)$, then $π_{G}(S)$ is the maximum number of edge-disjoint spanning paths in $G$. It is proved [Graphs Combin., 37 (2021) 2521-2533] that deciding whether $π_G(S)\geq r$ is NP-complete for a given $S\subseteq V(G)$. For an integer $r$ with $2\leq r\leq n$, the $r$-path connectivity of a graph $G$ is defined as $π_{r}(G)=$min$\{π_{G}(S)|S\subseteq V(G)$ and $|S|=r\}$, which is a generalization of tree connectivity. In this paper, we study the $3$-path connectivity of the $k$-dimensional data center network with $n$-port switches $D_{k,n}$ which has significate role in the cloud computing, and prove that $π_{3}(D_{k,n})=\lfloor\frac{2n+3k}{4}\rfloor$ with $k\geq 1$ and $n\geq 6$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_13423 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Packing internally disjoint Steiner paths of data center networks Zhu, Wen-Han Hao, Rong-Xia Chang, Jou-Ming Lee, Jaeun Combinatorics Let $S\subseteq V(G)$ and $π_{G}(S)$ denote the maximum number $t$ of edge-disjoint paths $P_{1},P_{2},\ldots,P_{t}$ in a graph $G$ such that $V(P_{i})\cap V(P_{j})=S$ for any $i,j\in\{1,2,\ldots,t\}$ and $i\neq j$. If $S=V(G)$, then $π_{G}(S)$ is the maximum number of edge-disjoint spanning paths in $G$. It is proved [Graphs Combin., 37 (2021) 2521-2533] that deciding whether $π_G(S)\geq r$ is NP-complete for a given $S\subseteq V(G)$. For an integer $r$ with $2\leq r\leq n$, the $r$-path connectivity of a graph $G$ is defined as $π_{r}(G)=$min$\{π_{G}(S)|S\subseteq V(G)$ and $|S|=r\}$, which is a generalization of tree connectivity. In this paper, we study the $3$-path connectivity of the $k$-dimensional data center network with $n$-port switches $D_{k,n}$ which has significate role in the cloud computing, and prove that $π_{3}(D_{k,n})=\lfloor\frac{2n+3k}{4}\rfloor$ with $k\geq 1$ and $n\geq 6$. |
| title | Packing internally disjoint Steiner paths of data center networks |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2401.13423 |