Title | ||
---|---|---|
Edge-fault-tolerant Hamiltonicity of pancake graphs under the conditional fault model |
Abstract | ||
---|---|---|
The conditional fault model imposes a constraint on the fault distribution. For example, the most commonly imposed constraint for edge faults is that each vertex is incident with two or more non-faulty edges. In this paper, subject to this constraint, we show that an n-dimensional pancake graph can tolerate up to 2n-7 edge faults, while retaining a fault-free Hamiltonian cycle, where n=4. Previously, at most n-3 edge faults can be tolerated for the same problem, if the edge faults may occur anywhere without imposing any constraint. |
Year | DOI | Venue |
---|---|---|
2008 | 10.1016/j.tcs.2008.09.015 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
Cayley graph,n-dimensional pancake graph,n-3 edge fault,fault distribution,Edge-fault-tolerant Hamiltonicity,Pancake graph,fault-free Hamiltonian cycle,non-faulty edge,Fault tolerance,conditional fault model,edge fault,Hamiltonian cycle,Conditional fault model | Journal | 409 |
Issue | ISSN | Citations |
3 | Theoretical Computer Science | 4 |
PageRank | References | Authors |
0.40 | 26 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Ping-Ying Tsai | 1 | 49 | 3.82 |
Jung-Sheng Fu | 2 | 461 | 24.92 |
Gen-Huey Chen | 3 | 979 | 89.32 |