错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Packing internally disjoint Steiner paths of data center networks

  • Wen-Han Zhu,
  • Rong-Xia Hao,
  • Jou-Ming Chang,
  • Jaeun Lee

摘要

Let \(S\subseteq V(G)\) S V ( G ) and \(\pi _{G}(S)\) π G ( S ) denote the maximum number t of edge-disjoint paths \(P_{1},P_{2},\ldots ,P_{t}\) P 1 , P 2 , , P t in a graph G such that \(V(P_{i})\cap V(P_{j})=S\) V ( P i ) V ( P j ) = S for any \(i,j\in \{1,2,\ldots ,t\}\) i , j { 1 , 2 , , t } and \(i\ne j\) i j . If \(S=V(G)\) S = V ( G ) , then \(\pi _{G}(S)\) π 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 \(\pi _G(S)\ge r\) π G ( S ) r is NP-complete for a given \(S\subseteq V(G)\) S V ( G ) . For an integer r with \(2\le r\le n\) 2 r n , the r-path connectivity of a graph G is defined as \(\pi _{r}(G)=\) π r ( G ) = min \(\{\pi _{G}(S)|S\subseteq V(G)\) { π G ( S ) | S V ( G ) and \(|S|=r\}\) | 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}\) D k , n which has signification role in the cloud computing, and prove that \(\pi _{3}(D_{k,n})=\lfloor \frac{2n+3k}{4}\rfloor\) π 3 ( D k , n ) = 2 n + 3 k 4 with \(k\ge 0\) k 0 and \(n\ge 3\) n 3 .