Hill Publishing Group | contact@hillpublisher.com

Hill Publishing Group

Location:Home / Journals / Journal of Applied Mathematics and Computation /

DOI:http://dx.doi.org/10.26855/jamc.2021.12.003

A New Multi-Objective Evolutionary Approach to Graph Coloring and Channel Allocation Problems

Date: October 14,2021 |Hits: 100 Download PDF How to cite this paper

S. Balakrishnan1, Tamilarasi Suresh2, Raja Marappan3,*

1Dr MGR Educational and Research Institute, Maduravoyal, Chennai, India.

2Department of Information Technology, St. Peter’s Institute of Higher Education and Research, Avadi, Chennai, India.  

3School of Computing, SASTRA Deemed University, Thanjavur, Tamil Nadu, India.

*Corresponding author: Raja Marappan

Abstract

Recent years, a large amount of graph coloring algorithms have been applied in different disciplines and engineering.  This paper exhibits a new multi-objective evolutionary algorithm using the new evolutionary operators with multi-objectives in finding the solution to graph coloring and channel allocation.  Clique, a maximal connected complete subgraph of a given graph is obtained in solving channel allocation problem.  The outcomes of the devised evolutionary method are compared with other recent approaches.  Multiple better gene sequences are selected and are applying the subsequent crossover and mutation operations with multiple objectives.  The devised operators significantly minimize the problem search space and average generations compared to the standard genetic algorithm.  The proposed operators achieve better solution compared to some of the existing well known methods.  The expected performance measures are also increased while minimizing the expected generations.  The proposed operators can also be applied in solving special engineering applications of graph coloring.

References

[1] Balakrishnan, R. and Ranganathan, K. (2000). A Textbook of Graph Theory. 1st Edition, Springer-Verlag, New York Publisher.

[2] Michael R. Garey and David S. (1979). Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York.

[3] Timir Maitra, Anindya J. Pal, Debnath Bhattacharyya, and Tai-hoon Kim. (2010). Noise Reduction in VLSI Circuits using Modified GA Based Graph Coloring. International Journal of Control and Automation, 3(2), (2010).

[4] Hertz, A. and Werra D. de. (1987). Using tabu search techniques for graph coloring. Computing, 39(4), 345-351.

[5] Charles Fleurent and Jacques A. Ferland. (1996). Genetic and hybrid algorithms for graph coloring. Annals of Operations Research, 63(3), 437-461.

[6] Christine, L. (2006). Mumford: New Order Based Crossovers for the Graph Coloring Problem. Parallel Problem Solving from Nature, 4193, 880-889.

[7] Anuj Mehrotra and Michael A. Trick. (1995). A Column Generation Approach for Graph Coloring. INFORMS Journal on Computing, 8, 344-354.

[8] Isabel Méndez-Díaz and Paula Zabala. A Branch and Cut algorithm for graph coloring. Discrete Applied Mathematics, 154, 826-847.

[9] Remi Monasson. (2004). On the Analysis of Backtrack Procedures for the Coloring of Random Graphs. Lect.Notes Phys., 650, 235-254.

[10] Lixia Han and Zhanli Han. (2010). A Novel Bi-objective Genetic Algorithm for the Graph Coloring Problem. 2nd International Conference on Computer Modeling and Simulation.

[11] Tamás Szép and Zoltán Ádám Mann. (2010). Graph coloring: The more colors, the better? 11th International Symposium on Computational Intelligence and Informatics (CINTI).

[12] Rudolph and Günter. (1998). Finite Markov Chain Results in Evolutionary Computation: A Tour d'Horizon. Fundamenta Informaticae, 35(1-4), 67-89.

[13] A. E. Eiben, J. K. Van Der Hauw, and J. I. Van Hemert. (1998). Graph Coloring with Adaptive Evolutionary Algorithms. Journal of Heuristics, 4, 25-46.

[14] Philippe Galinier and Alain Hertz. (2006). A survey of local search methods for graph coloring. Computers & Operations Research, 33(9), 2547-2562.

[15] David S. Johnson, Cecilia R. Aragon, Lyle A. McGeoch, and Catherine Schevon. (1991). An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning. Operations Research, 39(3).

[16] David S. Johnson and Michael A. Trick. (1993). Cliques, Coloring, and Satisfiability. American Mathematical Society, 26.

[17] Kazunori Mizuno and Seiichi Nishihara. (2008). Constructive generation of very hard 3-colorability instances. Discrete Applied Mathematics, 156, 218-229.

[18] Blanca Cases, Carmen Hernandez, Manuel Grana, and Alicia D’Anjou. (2008). On the ability of Swarms to compute the 3-coloring of graphs. Artificial Life, (2008).

[19] Manuel Graña, Blanca Cases, Carmen Hernandez, and Alicia D’Anjou. (2010). Further Results on Swarms Solving Graph Coloring. ICCSA 2010: Computational Science and Its Applications, 541-551.

[20] Yongquan Zhou, Hongqing Zheng, Qifang Luo, and Jinzhao Wu. (2013). An improved Cuckoo Search Algorithm for Solving Planar Graph Coloring Problem. Applied Mathematics & Information Sciences, 7(2), 785-792.

[21] Soma Saha, Rajeev Kumar, and Gyan Baboo. (2013). Characterization of graph properties for improved Pareto fronts using heuristics and EA for biobjective graph coloring problem. Applied Soft Computing, 13(5), 2812-2822.

[22] Steven Prestwich. (2008). Generalised graph colouring by a hybrid of local search and constraint programming. Discrete Applied Mathematics, 156, 148-158.

ha Liu, Yanfeng Wang, Xuncai Zhang, and Xianghong Cao. (2008). Modified PSO algorithm for solving planar graph coloring problem. Progress in Natural Science, 18, 353-357.

[27] The Graph Coloring instances. http://mat.gsia.cmu.edu/COLOR/instances.html.

[28] Hugo Hernández and Christian Blum. (2014). FrogSim: Distributed graph coloring in wireless ad hoc networks. Telecommunication Systems, 55(2), 211-223.

[29] Junichi Yoshino and Isao Ohtomo. (2005). Study on efficient channel assignment method using the genetic algorithm for mobile communication systems. Soft Computing, 9(2), 143-148.

[30] Pablo San Segundo. (2012). A new DSATUR-based algorithm for exact vertex coloring. Computers & Operations Research, 39(7), 1724-1733.

[31] Philippe Galinier and Jin-Kao Hao. (1999). Hybrid Evolutionary Algorithms for Graph Coloring. Journal of Combinatorial Optimization, 3(4), 379-397.

[32] Raja Marappan and Gopalakrishnan Sethumadhavan. (2013). A new genetic algorithm for graph coloring. 5th International Conference on Computational Intelligence, Modelling and Simulation, 49-54, (2013).

[33] Gopalakrishnan Sethumadhavan and Raja Marappan. (2013). A Genetic Algorithm for Graph Coloring using Single Parent Conflict Gene Crossover and Mutation with Conflict Gene Removal Procedure. IEEE International Conference on Computational Intelligence and Computing Research, 350-355, (2013).

[34] Xiang’en Chen, Yue Zu, Jin Xu, Zhiwen Wang, and Bing Yao. (2011). Vertex-Distinguishing E-Total Colorings of Graphs. Arabian Journal for Science and Engineering, 36(8), 1485-1500, (2011).

[35] Lewis, R. M. R. (2016). A Guide to Graph Coloring, Algorithms and Applications. Springer International Publishing Switzerland (2016).

[36] Marc Demange, Tınaz Ekim, Bernard Ries, and Cerasela Tanasescu. (2014). On some applications of the selective graph coloring problem. European Journal of Operational Research, (2014).

[37] Marc Demange, Tınaz Ekim, and Bernard Ries. (2015). On the minimum and maximum selective graph coloring problems in some graph classes. Discrete Applied Mathematics, (2015).

[38] Shih Heng Cheng and Ching Yao Huang. (2013). Coloring-Based Inter-WBAN Scheduling for Mobile Wireless Body Area Networks. IEEE Transactions on Parallel and Distributed Systems, 24(2), (2013).

[39] Elmahdi Driouch and Wessam Ajib. (2013). Downlink Scheduling and Resource Allocation for Cognitive Radio MIMO Networks. IEEE Transactions on Vehicular Technology, 62(8), (2013).

[40] Elmahdi Driouch and Wessam Ajib. (2012). Efficient Scheduling Algorithms for Multiantenna CDMA Systems. IEEE Transactions on Vehicular Technology, 61(2), (2012). 

[41] Matti Peltomäki, Juha-Matti Koljonen, Olav Tirkkonen, and Mikko Alava. (2012). Algorithms for Self-Organized Resource Allocation in Wireless Networks. IEEE Transactions on Vehicular Technology, 61(1), (2012).

[42] Lynn Takeshita. (2016). Coloring Signed Graphs, (2016).

[43] Edita Macajov, Andre Raspaud, and Martin Skoviera. (2016). The chromatic number of a signed graph. 

[44] Mohamed Abdelfattah and Ahmed Shawish. (2016). Automated Academic Schedule Builder for University’s Faculties. Proceedings of the World Congress on Engineering, (2016).

[45] Sandeep Saharan and Ravinder Kumar. (2016). Graph Coloring based Optimized Algorithm for Resource Utilization in Examination Scheduling. Applied Mathematics & Information Sciences, (2016).

[46] Ferdous M. O. Tawfiq and Kholoud Khalid S. Al-qahtani. (2016). Graph Coloring Applied to Medical Doctors Schedule. The 10th International Conference on Advanced Engineering Computing and Applications in Sciences, (2016).

[47] Simon Thevenin, Nicolas Zufferey, and Jean-Yves Potvin. (2016). Graph multi-coloring for a job scheduling application. CIRRELT, (2016).

[48] Bing Zhou. (2016). On the Maximum Number of Dominating Classes in Graph Coloring. Open Journal of Discrete Mathematics, (2016).

[49] Serge Gaspers and Edward J. Lee. (2016). Faster Graph Coloring in Polynomial Space. 

[50] Angelini, P., Bekos, M. A., De Luca, F., Didimo, W., Kaufmann, M., Kobourov, S., Montecchiani, F., Raftopoulou, C. N., Roselli, V., and Symvonis, A. (2017). Vertex-Coloring with Defects. Journal of Graph Algorithms and Applications, (2017).

[51] Murat Aslan and Nurdan Akhan Baykan. (2016). A Performance Comparison of Graph Coloring Algorithms. International Journal of Intelligent Systems and Applications in Engineering, (2016).

[52] Severino F. Galán. (2017). Simple decentralized graph coloring. Computational Optimization and Applications, (2017).

[53] T. Veeramakali, S. Jayashri, and S. Prabu. (2017). Intelligent dynamic spectrum allocation with bandwidth flexibility in cognitive radio network. Cluster Computing, 20: 1575-1586, (2017).

[54] I. Nelson, C. Annadurai, R. Kalidoss, and B. Partibane. (2017). Mitigation of co-channel interferences in cognitive multi-carrier code division multiple access system by singular value decomposition techniques. Cluster Computing. DOI: 10.1007/s10586-017-0997-y (2017).

[55] Xuesong Yan, Hanmin Liu, Zhixin Zhu, and Qinghua Wu. (2017). Hybrid genetic algorithm for engineering design problems. Cluster Computing, 20: 263-275.

[56] Xiangyu Meng, Liyan Dong, Yongli Li, and WilliamW. Guo. (2017). A genetic algorithm using K-path initialization for community detection in complex networks. Cluster Computing, 20: 311-320.

[57] Marappan, R. and Sethumadhavan, G. (2018). Solution to graph coloring using genetic and tabu search procedures. Arab J Sci Eng., 2018, 43, 525-542. Doi: https://doi.org/10.1007/s13369-017-2686-9.

[58] Marappan, R. and Sethumadhavan, G. (2020). Complexity analysis and stochastic convergence of some well-known evolutionary operators for solving graph coloring problem. Mathematics, 2020, 8, 303. doi: https://doi.org/10.3390/math8030303.

How to cite this paper

A New Multi-Objective Evolutionary Approach to Graph Coloring and Channel Allocation Problems

How to cite this paper: S. Balakrishnan, Tamilarasi Suresh, Raja Marappan. (2021) A New Multi-Objective Evolutionary Approach to Graph Coloring and Channel Allocation ProblemsJournal of Applied Mathematics and Computation5(4), 252-263.

DOI: http://dx.doi.org/10.26855/jamc.2021.12.003

Free HPG Newsletters

Add your e-mail address to receive free newsletters from Hill Publishing Group.

Contact us

Hill Publishing Group

8825 53rd Ave

Elmhurst, NY 11373, USA

E-mail: contact@hillpublisher.com

Copyright © 2019 Hill Publishing Group Inc. All Rights Reserved.