TY - GEN

T1 - Fault-free pairwise independent Hamiltonian paths on faulty hypercubes

AU - Hsieh, Sun Yuan

PY - 2006

Y1 - 2006

N2 - A Hamiltonian path in G is a path which contains every vertex of G exactly once. Two Hamiltonian paths P1= 〈u1, u2, . . ., un〉 and P2 = 〈v1, v 2, . . ., vn〉 of G are said to be independent if u1 = v1, un = vn, and ui ≠ vi for all 1 < i < n. A set of Hamiltonian paths {P 1, P2, . . ., Pk} of G are mutually independent if any two different Hamiltonian paths in the set are independent. It is well-known that an n-dimensional hypercube Qn is bipartite with two partite sets of equal-size. Let F be the set of faulty edges of Qn such that |F| ≤ n -2. In this paper, we show that Qn - F contains (n - |F| - 1)-mutually independent Hamiltonian paths between any two vertices from different partite sets, where n ≥ 2.

AB - A Hamiltonian path in G is a path which contains every vertex of G exactly once. Two Hamiltonian paths P1= 〈u1, u2, . . ., un〉 and P2 = 〈v1, v 2, . . ., vn〉 of G are said to be independent if u1 = v1, un = vn, and ui ≠ vi for all 1 < i < n. A set of Hamiltonian paths {P 1, P2, . . ., Pk} of G are mutually independent if any two different Hamiltonian paths in the set are independent. It is well-known that an n-dimensional hypercube Qn is bipartite with two partite sets of equal-size. Let F be the set of faulty edges of Qn such that |F| ≤ n -2. In this paper, we show that Qn - F contains (n - |F| - 1)-mutually independent Hamiltonian paths between any two vertices from different partite sets, where n ≥ 2.

UR - http://www.scopus.com/inward/record.url?scp=33845191286&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33845191286&partnerID=8YFLogxK

U2 - 10.1007/11859802_32

DO - 10.1007/11859802_32

M3 - Conference contribution

AN - SCOPUS:33845191286

SN - 3540400567

SN - 9783540400561

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 373

EP - 379

BT - Advances in Computer Systems Architecture - 11th Asia-Pacific Conference, ACSAC 2006, Proceedings

PB - Springer Verlag

T2 - 11th Asia-Pacific Conference on Advances in Computer Systems Architecture, ACSAC 2006

Y2 - 6 September 2006 through 8 September 2006

ER -