@article {IOPORT.05610286,
    author       = {Dvo\v r\'ak, Tom\'a\v s and Koubek, V\'aclav},
    title        = {Long paths in hypercubes with a quadratic number of faults.},
    year         = {2009},
    journal      = {Information Sciences},
    volume       = {179},
    number       = {21},
    issn         = {0020-0255},
    pages        = {3763-3771},
    publisher    = {Elsevier Science Inc. (North-Holland), New York, NY},
    doi          = {10.1016/j.ins.2009.06.029},
    abstract     = {Summary: 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)=\varTheta (n^{2})$ such that if $f\leqslant \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\leqslant \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.},
    identifier   = {05610286},
}