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