P. Ramanathan et S. Chalasani, RESOURCE PLACEMENT WITH MULTIPLE ADJACENCY CONSTRAINTS IN K-ARY N-CUBES, IEEE transactions on parallel and distributed systems, 6(5), 1995, pp. 511-519
Citations number
9
Categorie Soggetti
System Science","Engineering, Eletrical & Electronic","Computer Science Theory & Methods
The problem of placing resources in a k-ary n-cube (k > 2) is consider
ed in this paper. For a given j greater than or equal to 1, resources
are placed such that each nonresource node is adjacent to j resource n
odes. We first prove that perfect j-adjacency placements are impossibl
e in k-ary n-cubes if n < j < 2n. Then, we show that a perfect j-adjac
ency placement is possible in k-ary n-cubes when one of the following
two conditions is satisfied: 1) if and only if j equals 2n and k is ev
en, or 2) if 1 less than or equal to j less than or equal to n and the
re exist integers q and r such that q divides k and q(r) - 1 = 2n/j. I
n each case, we describe an algorithm to obtain perfect j-adjacency pl
acements. We also show that these algorithms can be extended under cer
tain conditions to place j distinct types of resources in a such way t
hat each nonresource node is adjacent to a resource node of each type.
For the cases when perfect j-adjacency placements are not possible, w
e consider approximate j-adjacency placements. We show that the number
of copies of resources required in this case either approaches a theo
retical lower bound on the number of copies required for any j-adjacen
cy placement or is within a constant factor of the theoretical lower b
ound for large k.