Thumbnail
Access Restriction
Open

Author Solano, Geoffrey A. ♦ Caro, Jaime D. L.
Source CiteSeerX
Content type Text
File Format PDF
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Hamming Network ♦ Ith Johnson Network ♦ Johnson Network ♦ Johnson Scheme Sgi ♦ Ith Graph ♦ Graph Gi ♦ Hamming Distance ♦ Vertex Set ♦ Johnson Scheme ♦ Combined Ith Graph ♦ Algorithm Structure ♦ Association Scheme ♦ Interesting Approach ♦ Johnson Distance ♦ Coordinate Position ♦ Hamming Graph ♦ Different Network ♦ Hamming Scheme ♦ Johnson Graph Gi ♦ Johnson Scheme Gi
Abstract Abstract:- Embedding of graphs is an important and interesting approach to parallel computing. Generally it can be used to model simulation of networks and algorithm structures on different networks. This paper shows that there is an embedding of the Johnson Networks into the Hamming Network. The vertex set of the Johnson Scheme G(n,k) is the set of all k-subsets of a fixed n-set. Two vertices A and B in G(n,k) are adjacent if A∩B =k-1. The ith graph of the Johnson Scheme Gi(n,k) is an extension of G(n,k) such that vertices are adjacent if they are they are i–related, that is, if A∩B =k-i. i is referred to as the Johnson Distance. The combined ith graphs of the Johnson Scheme SGi(n) is the graph formed by the union of all the graphs Gi(n,k) where 0<k<n. A Johnson Network is a network modeled after Johnson graph Gi(n,k). The Hamming Scheme H(n,q,r) is an association scheme whose vertex set Qn is the set of all words of length n over the alphabet Q of q symbols. Two vertices are adjacent if and only if they are r-related, that is, if they differ in exactly r coordinate positions where r is referred to as the Hamming Distance. A Hamming Network is a network modeled after the Hamming graph. This paper shows that every Johnson Network modeled after Gi(n,k) can also be embedded into the Hamming Network modeled after H(n,2,2i). This is done by showing that there is an embedding of the combined ith graphs of the Johnson Scheme SGi(n), into the Hamming Network H(n,q,r), when q=2 and r=2i..
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article