Name
Abstract | ||
|---|---|---|
A fault-free path in the n-dimensional hypercube Q"n with f faulty vertices is said to be long if it has length at least 2^n-2f-2. Similarly, a fault-free cycle in Q"n is long if it has length at least 2^n-2f. If all faulty vertices are from the same bipartite class of Q"n, such length is the best possible. We show that for every set of at most 2n-4 faulty vertices in Q"n and every two fault-free vertices u and v satisfying a simple necessary condition on neighbors of u and v, there exists a long fault-free path between u and v. This number of faulty vertices is tight and improves the previously known results. Furthermore, we show for every set of at most n^2/10+n/2+1 faulty vertices in Q"n where n=15 that Q"n has a long fault-free cycle. This is a first quadratic bound, which is known to be asymptotically optimal. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.ins.2009.06.011 | Inf. Sci. |
Keywords | Field | DocType |
long fault-free path,simple necessary condition,n-dimensional hypercube,bipartite class,asymptotically optimal,fault-free cycle,faulty vertex,long fault-free cycle,fault-free vertices u,long path,fault-free path,hypercube,satisfiability | Discrete mathematics,Combinatorics,Vertex (geometry),Existential quantification,Bipartite graph,Quadratic equation,Asymptotically optimal algorithm,Mathematics,Hypercube | Journal |
Volume | Issue | ISSN |
179 | 20 | 0020-0255 |
Citations | PageRank | References |
18 | 0.94 | 16 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jiří Fink | 1 | 82 | 9.00 |
| Petr Gregor | 2 | 178 | 19.79 |