Special Issue: Computer Networks and Distributed Computing

• Architecture and High Performance Computer Systems • Previous Articles     Next Articles

A General Approach to {\it\bfseries L$($h,k$)$}-Label Interconnection Networks

Tiziana Calamoneri, Saverio Caminiti, and Rossella Petreschi   

  1. Department of Computer Science, Sapienza University of Rome, Italy
  • Received:2007-03-22 Revised:2008-04-24 Online:2008-07-10 Published:2008-07-10

Given two non-negative integers $h$ and $k$, an $L(h,k)$-{\em 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\v{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 \times n)$-{\em 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.

Key words: logic for artificial intelligence(AI); automated theorem proving; logic programming; Horn and non-Horn sets; predicate renaming; NP-completeness;

[1] Roberts F S. From Garbage to Rainbows: Generalizations of Graph Coloring and Their Applications. {Graph Theory, Combinatorics, and Applications}, 2, Alavi Y, Chartrand G, Oellermann O R, Schwenk A J (eds.), 2, New York: Wiley, 1991, pp.1031--1052.
[2]} Jensen T R, Toft B. Graph Coloring Problems. New York: John Wiley \& Sons, 1995.
[3]} Griggs J R, Yeh R K. Labeling graphs with a condition at distance 2. {\it SIAM Journal on Discrete Mathematics} 1992, 5(4): 586--595.
[4]} Georges J P, Mauro D W. Generalized vertex labelings with a condition at distance two. {\em Congressus Numerantium}, 1995, 109: 141--159.
[5]} Calamoneri T. Exact solution of a class of frequency assignment problems in cellular networks. {\em Discrete Mathematics $\&$ Theoretical Computer Science}, 2006, 8: 141--158.
[6]} Calamoneri T, Pelc A, Petreschi R: Labeling trees with a condition at distance two. {\em Discrete Mathematics}, 2006, 306(14): 1534--1539.
[7]} Georges J P, Mauro D W. Labeling trees with a condition at distance two. {\em Discrete Mathematics}, 2003, 269(1-3): 127--148.
[8]} Georges J P, Mauro D W, Stein M I. Labeling products of complete graphs with a condition at distance two. {\em SIAM Journal on Discrete Mathematics}, 2001, 14(1): 28--35.
[9]} J van den Heuvel, R A Leese, M A Shepherd. Graph labelling and radio channel assignment. {\em Journal of Graph Theory}, 1998, 29(4): 263--283.
[10]} Agnarsson G, Halld\'{o}rsson M M. Coloring powers of planar graphs. {\em SIAM Journal on Discrete Mathematics}, 2003, 16(4): 651--662.
[11]} Hale W K. Frequency assignment: Theory and application. {\em Proceedings of the IEEE}, 1980, 68(12): 1487--1514.
[12]} K I Aardal, S P M van Hoesel, A M C A Koster, C Mannino, A Sassano. Models and solution techniques for frequency assignment problems. {ZIB-Report 01-40, Konrad-Zuse-Zentrum fur Informationstechnik Berlin}, 2001.
[13]} H L Bodlaender, T Kloks, R B Tan, J van Leeuwen. Lambda coloring of graphs. In {\em Proc. 17th Annual Symposium on Theoretical Aspects of Computer Science $($STACS 2000$)$}, Lille, France, {\it LNCS} 1770, Feb. 2000, pp.395--406.
[14]} Calamoneri T, Petreschi R. $L(2,1)$-labeling of planar graphs. {\em Journal on Parallel and Distributed Computing}, 2004, 64(3): 414--426.
[15]} Calamoneri T, Petreschi R. $\lambda$-coloring matrogenic graphs. {\em Discrete Applied Mathematics}, 2006, 154: 2445--2457.
[16]} Chang G J, Kuo D. The $L(2,1)$-labeling problem on graphs. {\em SIAM Journal on Discrete Mathematics}, 1996, 9: 309--316.
[17]} Fiala J, Kloks T, Kratochv\'{i}l J. Fixed-parameter complexity of $\lambda$-colorings. In {\em Proc. Graph Theoretic Concepts in Computer Science $($WG'99$)$}, {\it LNCS} 1665, 1999, pp.350--363.
[18]} Murphey R A, Pardalos P M, Resende M G C. Frequency Assignment Problems. {Handbook of Combinatorial Optimization}, Du D-Z, Pardalos P M (eds.), Kluwer Academic Publishers, 1999, pp.295--377.
[19]} Sakai D. Labeling chordal graphs: Distance 2 condition. {\em SIAM Journal on Discrete Mathematics}, 1994, 7(1): 133--140.
[20]}Shepherd M. Radio channel assignment [Dissertation]. Merton College, Oxford, 1998.
[21]} Whittlesey M A, Georges J P, Mauro D W. On the $\lambda$ number of $Q_n$ and related graphs. {\em SIAM Journal on Discrete Mathematics}, 1995, 8(4): 499--506.
[22]} Calamoneri T. The $L(h,k)$-labelling problem: A survey and annotated bibliography. {\em The Computer Journal}, 2006, 49(5): 585--608, http://www.dsi.uniroma1.it/$\sim$calamo/survey.html.
[23]} Leighton F T. Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Morgan Kaufmann, 1992.
[24]} Preparata F P, Vuillemin J. The cube-connected cycles: A versatile network for parallel computation. {\em Communications of ACM}, 1981, 24(5): 300--309.
[25]} Calamoneri T, Massini A. Efficient algorithms for checking the equivalence of multistage interconnection networks. {\em Journal on Parallel and Distributed Computing}, 2004, 64(1): 135--150.
[26]} Calamoneri T, Petreschi R. A new 3D representation of trivalent Cayley networks. {\em Information Processing Letters}, 1997, 61(5): 247--252.
[27]} Vadapalli P, Srimani P K. Trivalent Cayley graphs for interconnection networks. {\em Information Processing Letters}, 1995, 54(6): 329--335.
[1] Zhao-Peng Li, Yu Zhang, and Yi-Yun Chen. A Shape Graph Logic and A Shape System [J]. , 2013, 28(6): 1063-1084.
[2] Jie Wang, Shi-Er Ju, and Chun-Nian Liu. Agent-Oriented Probabilistic Logic Programming [J]. , 2006, 21(3): 412-417 .
[3] Jian-Er Chen. Parameterized Computation and Complexity: A New Approach Dealing with NP-Hardnes [J]. , 2005, 20(1): 0-0.
[4] Jin-Zhao Wu and Harald Fecher. Symmetric Structure in Logic Programming [J]. , 2004, 19(6): 0-0.
[5] Zhen-Hua Duan and Maciej Koutny. A Framed Temporal Logic Programming Language [J]. , 2004, 19(3): 0-0.
[6] Hao Lin, Ze-Feng Zhang, Qiang-Feng Zhang,Dong-Bo Bu, and Ming Li. A Note on the Single Genotype Resolution Problem [J]. , 2004, 19(2): 0-0.
[7] Luca Aceto, Jens A. Hansen, Anna Ingolfsdottir, Jacob Johnsen and John Knudsen. The Complexity of Checking Consistency of Pedigree Information and Related Problems [J]. , 2004, 19(1): 0-0.
[8] ZHANG Xiaolong (张晓龙) and Masayuki Numao. Toward Effective Knowledge Acquisition with First-Order Logic Induction [J]. , 2002, 17(5): 0-0.
[9] NIE Xumin; GUO Qing;. Renaming a Set of Non-Horn Clauses [J]. , 2000, 15(5): 409-415.
[10] NIE Xumin(聂旭民)and GUO Qing(郭青). Renaming a Set of Non-Horn Clauses [J]. , 2000, 15(5): 0-0.
[11] Wang Kewen; Chen Huowang; Wu Quanyuan;. The Least Fixpoint Transformation for Disjunctive Logic Programs [J]. , 1998, 13(3): 193-201.
[12] Zhang Xiaolong; Masayuki Numao;. An Efficient Multiple Predicate Learner [J]. , 1998, 13(3): 268-278.
[13] Zhang Chenghong; Hu Yunfa; Shi Baile;. A Reasoning Mechanism for DeductiveObject-Oriented Databases [J]. , 1997, 12(4): 337-345.
[14] Shen Ningchuan; Li Wei;. R-Calculus for ELP:An Operational Approach to Knowledge Base Maintenance [J]. , 1997, 12(1): 17-28.
[15] Xu Dianxiang; Zheng Guoliang;. Towards a Declarative Semantics of Inheritance with Exceptions [J]. , 1996, 11(1): 61-71.
Full text



[1] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[2] Wang Hui; Liu Dayou; Wang Yafei;. Sequential Back-Propagation[J]. , 1994, 9(3): 252 -260 .
[3] Dong-Hong Han, Guo-Ren Wang, Chuan Xiao, and Rui Zhou. Load Shedding for Window Joins over Streams[J]. , 2007, 22(2): 182 -189 .
[4] Yong-Xuan Lai, Yi-Long Chen, and Hong Chen. PEJA: Progressive Energy-Efficient Join Processing for Sensor Networks[J]. , 2008, 23(6 ): 957 -972 .
[5] Liu-Xin Zhang (张柳新), Member, CCF, Ming-Tao Pei (裴明涛), Member, CCF and Yun-De Jia (贾云得), Senior Member, CCF. Multiview Visibility Estimation for Image-Based Modeling[J]. , 2011, 26(6): 1000 -1010 .
[6] Wu Yang Guo-Wei Shen, Wei Wang, Liang-Yi Gong, Miao Yu, Guo-Zhong Dong. Anomaly Detection in Microblogging via Co-Clustering[J]. , 2015, 30(5): 1097 -1108 .
[7] Chun-Meng Kang, Lu Wang, Yan-Ning Xu, Xiang-Xu Meng, Yuan-Jie Song. Adaptive Photon Mapping Based on Gradient[J]. , 2016, 31(1): 217 -224 .
[8] Jing-Ya Zhou, Jian-Xi Fan, Cheng-Kuan Lin, Bao-Lei Cheng. A Cost-Efficient Approach to Storing Users' Data for Online Social Networks[J]. Journal of Computer Science and Technology, 2019, 34(1): 234 -252 .
[9] Meng-Ke Yuan, Long-Quan Dai, Dong-Ming Yan, Li-Qiang Zhang, Jun Xiao, Xiao-Peng Zhang. Fast and Error-Bounded Space-Variant Bilateral Filtering[J]. Journal of Computer Science and Technology, 2019, 34(3): 550 -568 .
[10] Hui-Si Wu, Meng-Shu Liu, Lu-Lu Yin, Ping Li, Zhen-Kun Wen, Hon-Cheng Wong. Automatic Video Segmentation Based on Information Centroid and Optimized SaliencyCut[J]. Journal of Computer Science and Technology, 2020, 35(3): 564 -575 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved