Publication at Faculty of Mathematics and Physics |
2009
Abstract
A path between distinct vertices u and v of the n-dimensional hypercube Q(n) avoiding a given set of f faulty vertices is called long if its length is at least 2^n-2f-2. We present a function phi(n) = Theta(n^2) such that if f {= phi(n) then there is a long fault-free path between every pair of distinct vertices of the largest fault-free block of Q(n).
Moreover, the bound provided by phi(n) is asymptotically optimal. Furthermore, we show that assuming f {= phi(n), the existence of a long fault-free path between an arbitrary pair of vertices may be verified in polynomial time with respect to n and, if the path exists, its construction performed in linear time with respect to its length.