Chromatic sets of power graphs and their application to resource placement in multicomputer networks

✍ Scribed by N. Imani; H. Sarbazi-Azad; S.G. Akl; P. Moinzadeh

• Book ID: 104008475
• Publisher: Elsevier Science
• Year: 2009
• Tongue: English
• Weight: 573 KB
• Volume: 58
• Category: Article
• ISSN: 0898-1221
• DOI: 10.1016/j.camwa.2009.01.043

✦ Synopsis

a b s t r a c t

In this paper, using the chromatic properties of power graphs we propose a new approach for placing resources in symmetric networks. Our novel placement scheme guarantees a perfect placement when such a solution is feasible in the topology, while in general it answers the question of k-resource placement at a distance d where each non-resource node is able to access k resource nodes within at most d hops away. We define a quasiperfect graph as a graph whose clique number and chromatic number are equal. We derive important properties of quasi-perfect graphs and use them to find a solution for the resource placement problem. We have also applied the proposed method to find a distant resource placement in the popular hypercube network as an example. We have also considered the problem of sparse resource placement.