Abstract
The L(h, k)-labeling is an assignment of frequencies to the transmitters/receivers of a multihop radio network such that ‘close’transmitters must have frequencies which differ by at least k, and ‘very close’ transmitters must have frequencies which differ by at least h. The span of an L(h,k)-labeling is the difference between the largest and the smallest assigned frequency. In this paper we study the L(h, k)-labeling problem of cellular graphs, seeking those with minimum span for each value of k and h ≥ k.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aardal, K.I., van Hoesel, S.P.M., Koster, A.M.C.A., Mannino, C., Sassano, A.: Models and Solution Techniques for Frequency Assignment Problems. ZIB-Report 01-40, Konrad-Zuse-Zentrum fur Informationstechnik Berlin (2001)
Bertossi, A.A., Bonuccelli, M.A.: Code Assignment for Hidden Terminal Interference Avoidance in Multihop Packet Radio Networks. IEEE/ACM Trans. On Networking 3, 441–449 (1995)
Bertossi, A.A., Pinotti, C.M., Tan, R.B.: Channel assignment with separation for interference avoidance in wireless networks. IEEE Transactions on Parallel and Distributed Systems (in press); Preliminary version in ACM Workshop DIAL M 2000 (2000)
Bodlaender, H.L., Kloks, T., Tan, R.B., van Leeuwen, J.: λ-Coloring of Graphs. In: Reichel, H., Tison, S. (eds.) STACS 2000. LNCS, vol. 1770, pp. 395–406. Springer, Heidelberg (2000)
Calamoneri, T., Petreschi, R.: L(2, 1)-Labeling of Planar Graphs (Extended Abstract). In: Proceedings of 5th ACM Int. Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIAL M), pp. 28–33 (2001)
Calamoneri, T., Petreschi, R.: On the Radiocoloring Problem. In: Das, S.K., Bhattacharya, S. (eds.) IWDC 2002. LNCS, vol. 2571, pp. 118–127. Springer, Heidelberg (2002)
Calamoneri, T., Petreschi, R.: λ-Coloring Unigraphs. In: Rajsbaum, S. (ed.) LATIN 2002. LNCS, vol. 2286, pp. 236–247. Springer, Heidelberg (2002)
Calamoneri, T., Pelc, A., Petreschi, R.: Labeling trees with a condition at distance two. In: Proceedings of R.C. Bose Centenary Symp. on Discr. Math. And Applications. electronic notes in discrete mathemathics (2002)
Calamoneri, T., Vocca, P.: On the Approximability of the L(h, k)-Labelling Problem (2003) (manuscript)
Chang, G.J., Kuo, D.: The L(2, 1)-labeling Problem on Graphs. SIAM J. Disc. Math. 9, 309–316 (1996)
Fotakis, D.A., Nikoletseas, S.E., Papadoulou, V.G., Spirakis, P.G.: NP-completeness Results and Efficient Approximations for Radiocoloring in Planar Graphs. In: Nielsen, M., Rovan, B. (eds.) MFCS 2000. LNCS, vol. 1893, p. 363. Springer, Heidelberg (2000)
Georges, J.P., Mauro, D.W.: Some results on λ j k -numbers of the products of complete graphs. Congr. Numer. 140, 141–160 (1999)
Georges, J.P., Mauro, D.W., Stein, M.I.: Labeling products of complete graphs with a condition at distance two. SIAM J. Discr. Math. 14, 28–35 (2000)
Griggs, J.R., Yeh, R.K.: Labeling graphs with a Condition at Distance 2. SIAM J. Disc. Math. 5, 586–595 (1992)
van den Heuvel, J., Leese, R.A., Shepherd, M.A.: Graph Labelling and Radio Channel Assignment. Journal of Graph Theory 29, 263–283 (1998)
Koster, A.M.C.A.: Frequency Assignment. Ph.D. thesis, Universiteit Maastricht (1999)
Liu, D., Yeh, R.K.: On distance two labelings of graphs. Ars Combinatoria 47, 13–22 (1997)
Molloy, M., Salavatipour, M.R.: Frequency channel assignment on planar networks. In: Möhring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol. 2461, pp. 736–747. Springer, Heidelberg (2002)
Murphey, R.A., Pardalos, P.M., Resende, M.G.C.: Frequency Assignment Problems. In: Du, D.-Z., Pardalos, P.M. (eds.) Handbook of Combinatorial Optimization, pp. 295–377. Kluwer Academic Publishers, Dordrecht (1999)
Sakai, D.: Labeling Chordal Graphs: Distance Two Condition. SIAM J. Disc. Math. 7, 133–140 (1994)
Sen, A., Roxborough, T., Medidi, S.: Upper and Lower Bounds of a Class of Channel Assignmet Problems in Cellular Networks. IEEE INFOCOM 1998 (1998)
Shepherd, M.: Radio Channel Assignment. Ph.D. thesis, Merton College, Oxford (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Calamoneri, T. (2003). Exact Solution of a Class of Frequency Assignment Problems in Cellular Networks. In: Blundo, C., Laneve, C. (eds) Theoretical Computer Science. ICTCS 2003. Lecture Notes in Computer Science, vol 2841. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-45208-9_14
Download citation
DOI: https://doi.org/10.1007/978-3-540-45208-9_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-20216-5
Online ISBN: 978-3-540-45208-9
eBook Packages: Springer Book Archive