Node disjoint path construction algorithm in the folded divide-and-swap cube

Key Points

The algorithm enables the construction of d + 2 node disjoint paths between two distinct nodes, highlighting its efficiency.
Maximum path length for these constructions does not exceed n + 9, indicating optimality within defined limits.
This work focuses on the one-to-one node disjoint path problem within the folded divide-and-swap cube framework.
Folded divide-and-swap cubes show potential as a robust topology for data center networks, supporting advanced algorithms.

Abstract

The folded divide-and-swap cube FDSC n ( n = 2 d , d ≥ 1) is a new hypercube variant, which has many superior properties compared to the hypercube. FDSC n is suitable as a candidate topology for data center networks. In this article, we investigate the one-to-one node disjoint path problem of FDSC n . We first present an algorithm to construct a path between any two distinct nodes u and v based on the structural characteristics of FDSC n . Then we develop an algorithm to build d + 2 node disjoint paths between any two different nodes in FDSC n , and show that the maximum length of these paths shall not exceed n + 9.

Node disjoint path construction algorithm in the folded divide-and-swap cube

Key Points

Abstract

Cite This Study