%0 Journal Article
%T A General Approach to L(h,k)-Label Interconnection Networks
A General Approach to {\it\bfseries L$($h,k$)$}-Label Interconnection Networks
%A Tiziana Calamoneri
%A Saverio Caminiti
%A Rossella Petreschi
%A
Tiziana Calamoneri
%A Saverio Caminiti
%A and Rossella Petreschi
%J 计算机科学技术学报
%D 2008
%I
%X 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. It is well known that the most common interconnection topologies, such as Butterfly-like, Bene·s, CCC, Trivalent Cayley networks, are all characterized by a similar structure: they have nodes organized as a matrix and connections are divided into layers. So we naturally introduce a new class of graphs, called (l × n)-multistage graphs, containing the most common interconnection topologies, on which we study the L(h, k)-labeling. A general algorithm for L(h, k)-labeling these graphs is presented, and from this method an efficient L(2, 1)-labeling for Butterfly and CCC networks is derived. Finally we describe a possible generalization of our approach. Work supported in part by Sapienza University of Rome (project “Parallel and Distributed Codes”).
%K multistage interconnection network
%K L(h
%K k)-labeling
%K channel assignment problem
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=F57FEF5FAEE544283F43708D560ABF1B&aid=5E22E9B4F6CBCC5383CF971BC92C9B50&yid=67289AFF6305E306&vid=EA389574707BDED3&iid=E158A972A605785F&sid=4A8412AEEC89236B&eid=00520952CD4BF212&journal_id=1000-9000&journal_name=计算机科学技术学报&referenced_num=0&reference_num=27