Computer Science MRP
Students currently enrolled in the Computer Science graduate program here at Brock University will be required to submit an electronic copy of their final Major Research Paper to this repository as part of graduation requirements.
If you are logged in please click on 'Submit a New Item to this Collection' to proceed.Once your MRP has been accepted in the Repository you will receive an email confirmation along with a link to your work
An Improved Sufficient Condition for Routing on the Hypercube with Blocking NodesWe 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.