A General Approach to L(h,k)-Label Interconnection networks

(Extended Abstract)

Given two non negative integers h and k, an L(h,k)-labeling of a graph G=(V,E) is a function from the set V to a set of colors, such that adjacent nodes take colors at distance at least h and nodes at distance 2 take colors at distance at least k. The aim of the L(h,k)-labeling problem is to minimize the greatest used color. Since the decisional version of this problem is NP-complete, it is important to investigate particular classes of graphs for which the problem can be efficiently solved. In this work the L(h,k)-labeling problem for a new class of graphs, called (l x n)-multistage graphs, is studied. These graphs are characterized to have nodes organized as a matrix and they include the most common interconnection topologies, such as Butterfly-like, Benes, CCC, Trivalent Cayley networks. The general algorithm presented in this paper leads to an efficient $L(2,1)$-labeling scheme for Butterfly and CCC networks.

PDF Files

Conference Version

Journal Version