Computer Science MRPhttp://hdl.handle.net/10464/145722023-06-07T21:33:48Z2023-06-07T21:33:48ZAn Improved Sufficient Condition for Routing on the Hypercube with Blocking NodesWang, Wenjiehttp://hdl.handle.net/10464/174962023-03-02T18:10:15ZAn Improved Sufficient Condition for Routing on the Hypercube with Blocking Nodes
Wang, Wenjie
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.