An Improved Sufficient Condition for Routing on the Hypercube with Blocking Nodes

Abstract

We study the problem of routing between two nodes in a hypercube with blocking nodes using shortest path. This problem has been previously studied by other researchers, they have proposed a few algorithms to solve the problem. Among the work done, one has found several sufficient conditions for such a path to exist. One such condition states that a shortest path between node 0^n and 1^n exists if the number of blocking nodes is less than n in an n-dimensional hypercube. We improve this condition by proposing the condition that if the size of a SDR (system of distinct representatives) for the blocking nodes is less than n, then a shortest path between the two nodes 0^n and 1^n exists. Since the number of blocking nodes can be greater than or equal to n, while the size of SDR is less than n, thus this result improves the previous sufficient condition.