The disjoint path cover in the data center network HSDC with prescribed vertices in each path.

The n -dimensional HSDC with the logic graph H n is one of the most attractive server-centric data center networks for high incremental scalability. The routing design in network topology is very important for information transmission. In particular, the application of disjoint path covers can solve various problems such as program code optimization and mapping parallel programs to parallel structures. H n consists of 2 n cliques and each two vertices in a clique are adjacent. For any vertex sets { x , u } and { y , v } in W and B , respectively, and any two disjoint vertex sets A 1 , A 2 in some clique, where (W , B) is a bipartition of H n , in this paper, we prove that, when | A i | ≠ 1 and A i ∩ { x , y , u , v } = ∅ for i = 1 , 2 , if | A 1 ∪ A 2 | ≤ n − 3 , then there exists an (x , y) -path P 1 and a (u , v) -path P 2 in H n passing through A 1 and A 2 , respectively, such that P 1 and P 2 have no common vertices and P 1 ∪ P 2 contains all vertices of H n. Then P 1 ∪ P 2 is called the 2-disjoint path cover in H n and we propose the efficient algorithms for the path design. Furthermore, we prove that our main result is optimal. • In the problem of data harvest and information transmission, it is very important to design the disjoint path cover in the logic graph of Data Center Network. • We consider the construction of 2-disjoint path cover such that each path should contain all prescribe vertices which have low probability of failure. • The efficient algorithms have been given and we prove that the number of prescribed vertices is not more than n − 3 and explain that this upper bound is sharp. [ABSTRACT FROM AUTHOR]