L(3,2,1)-Labeling on Graphs: Comparison between Greedy Heuristics and Genetic Algorithm

• Jhon Kennedy C. de L. Queiroz UFC
• Atílio G. Luiz UFC

DOI: https://doi.org/10.5753/eniac.2025.14495

Abstract

Several graph labeling problems have applications in the assignment of frequency channels to transmitters. One such problem is the L(3, 2, 1)-Labeling Problem, in which labels from the set {0, 1, . . . , k} are assigned to the vertices of a graph in such a way that, for any two vertices u, v ∈ V (G), the constraint |f(u)−f(v)| ≥ 4−dist(u, v) must be satisfied, where dist(u, v) denotes the distance between u and v in G. Since this problem is NP-complete, this work proposes heuristic and metaheuristic approaches to obtain approximate solutions. Two greedy algorithms and one genetic algorithm were implemented. The results show that the greedy approach is more efficient in terms of runtime, while the genetic algorithm produces higher-quality solutions.

References

Calamoneri, T. (2006). The l(h, k)-labelling problem: A survey and annotated bibliography. The Computer Journal, 49(5):585–608.

CELAR (2025). Celar radio link frequency assignment instances. [link]. Acesso em 2025.

Chia, M. L., Kuo, D., Yang, H. L. C. H., and Yeh, R. K. (2011). L(3,2,1) labeling of graphs. Taiwanese Journal of Mathematics, 15:2439–2457.

Clipperton, J., Gehrtz, J., Szaniszlo, Z., and Torkornoo, D. (2005). L(3,2,1)-labeling of simple graphs. In Proceedings of the 36th Southeastern International Conference on Combinatorics, Graph Theory and Computing, pages 1–14.

Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. (2009). Introduction to Algorithms. MIT press, 3 edition.

Duff, I. S., Grimes, R. G., and Lewis, J. G. (2025). Harwell-boeing sparse matrix collection. [link]. Acesso em 2025.

Florencio, D. G. and Luiz, A. G. (2021). Limites superiores para a rotulação-L(3,2,1) de grafos com grau máximo três. In Anais do LIII Simpósio Brasileiro de Pesquisa Operacional (SBPO), pages 11–15, João Pessoa, Brasil. Galoá.

Gen, M. and Cheng, R. (1997). Genetic Algorithms and Engineering Design. John Wiley & Sons, New York.

Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, Boston.

Griggs, J. R. and Yeh, R. K. (1992). Labelling graphs with a condition at distance 2. SIAM Journal on Discrete Mathematics, 5(4):586–595.

Hagberg, A. A., Schult, D. A., and Swart, P. J. (2008). Networkx: Python software for the analysis of networks. Disponível em: [link].

Hale, W. K. (1980). Frequency assignment: Theory and applications. Proceedings of the IEEE, 68(12):1497–1514.

Han, K. and Kim, C. (2008). Solving l(2,1)-labeling problem of graphs using genetic algorithms. The KIPS Transactions:PartB, 15B(2):131–136.

Hart, E., Ross, P., and Nelson, J. (2005). A survey of hybrid metaheuristics. Studies in Computational Intelligence, 1:1–26.

Holland, J. H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor, MI.

Jansky, D. (1977). Spectrum Management Techniques. Multi-volume EMC encyclopedia series. Don White Consultants.

Johnson, D. S. and Trick, M. A. (1996). Cliques, coloring, and satisfiability: Second dimacs implementation challenge. In DIMACS Series in Discrete Mathematics and Theoretical Computer Science, volume 26. American Mathematical Society.

Mitchell, M. (1998). An Introduction to Genetic Algorithms. MIT Press, Cambridge, MA.

Mumford, C. L. (2006). New order-based crossovers for the graph coloring problem. In Runarsson, T. P., Beyer, H.-G., Burke, E., Merelo-Guervós, J. J., Whitley, L. D., and Yao, X., editors, Parallel Problem Solving from Nature - PPSN IX, pages 880–889, Berlin, Heidelberg. Springer Berlin Heidelberg.

Murphey, R. A., Pardalos, P. M., and Resende, M. G. C. (1999). Frequency Assignment Problems, pages 295–377. Springer US, Boston, MA.

Panda, B. S. and Goel, P. (2010). Heuristic algorithms for the l(2,1)-labeling problem. Lecture Notes in Computer Science,Swarm, Evolutionary, and Memetic Computing, Not available:214–221.

Shao, J. and Liu, X. (2004). Labeling graphs with maximum degree three and four. Discrete Mathematics, 275(1-3):339–349.

Shao, Z. and Vesel, A. (2013). Integer linear programming model and satisfiability test reduction for distance constrained labellings of graphs: the case of l(3,2,1)labelling for products of paths and cycles. IET Communications, 7(8):715–720.