An Innovative Solution to the Map Coloring Problem Using the Malatya Vertex Coloring Algorithm

Öz

The map coloring problem is a classical NP-complete problem that requires adjacent regions to be colored differently and is encountered in many real-world applications. Numerous algorithms have been developed to solve this problem. In this study, the Malatya Vertex Coloring (MVC) Algorithm, which presents a novel and original approach to solving the problem, is applied. This algorithm aims to identify influential vertices to reduce the number of colors used in graphs and to complete the coloring process more efficiently. Additionally, the applicability of the algorithm to real-world problems is also evaluated. The MVC Algorithm calculates the Malatya Centrality value for each vertex in the graph; it selects the vertex with the highest value, colors it with a color different from its neighbors, and then removes it from the graph. This process continues until all vertices are colored. The algorithm has been successfully applied to maps of Asia, Europe, districts of Istanbul, Turkey, U.S. states, and the world, and the results demonstrate the effectiveness of the algorithm. The advantages of the MVC Algorithm include its predictability, as well as its ability to operate in polynomial time and space. In this respect, the MVC Algorithm offers an alternative solution approach to the classical Four Color Theorem in the context of the map coloring problem.

Anahtar Kelimeler

• Centrality
• graph coloring
• map coloring
• planar graph

Malatya Düğüm Renklendirme Algoritması Kullanılarak Harita Renklendirme Problemi için Yenilikçi Bir Çözüm

Öz

Harita renklendirme problemi, bitişik bölgelerin farklı renklerle boyanmasını gerektiren ve birçok gerçek hayat uygulamasında karşılaşılan klasik bir NP-tam problemdir. Bu problemin çözümü için birçok algoritma geliştirilmiştir. Bu çalışmada, ilgili problemin çözümüne yönelik yeni ve özgün bir yaklaşım ortaya koyan Malatya Vertex Coloring (MVC) Algoritması uygulanmıştır. Bu algoritma, graflarda kullanılan renk sayısını azaltmak için etkili düğümleri belirlemekte ve renklendirme sürecini daha kısa sürede tamamlamayı hedeflemektedir. Ayrıca algoritmanın, gerçek hayat problemlerine uygulanabilirliği de değerlendirilmiştir. MVC Algoritması, graf yapısındaki her düğüm için Malatya Merkezilik değerini hesaplar; en yüksek değere sahip düğümü seçerek komşularından farklı bir renkle boyar ve ardından bu düğümü graf üzerinden çıkarır. Bu işlem, tüm düğümler renklendirilene kadar devam etmektedir. Algoritma; Asya, Avrupa, İstanbul ilçeleri, Türkiye, ABD eyaletleri ve Dünya haritaları üzerinde başarıyla uygulanmış ve elde edilen sonuçlar algoritmanın etkinliğini ortaya koymuştur. MVC Algoritması’nın avantajları arasında öngörülebilir olması, polinom zamanda ve polinom uzayda çalışabilmesi yer almaktadır. Bu yönüyle, MVC Algoritması’nın harita renklendirme problemine ilişkin olarak klasik Dört Renk Teoremi’ne alternatif bir çözüm yaklaşımı sunduğu ortaya konulmuştur.

Anahtar Kelimeler

• Merkezilik
• graf renklendirme
• harita renklendirme
• malatya coloring
• düzlemsel graf.

Kaynakça

1. Fritsch R, Fritsch G. Four-Color Theorem. New York, NY, USA: Springer-Verlag; 1998.
2. Zhou Y, Zheng H, Luo Q, Wu J. An improved Cuckoo Search Algorithm for Solving Planar Graph Coloring Problem. Appl Math Inf Sci 2013; 7(2): 785-792.
3. Hale WK. Frequency assignment: Theory and applications. Proc IEEE 1980; 68(12): 1497-1514.
4. Ono S, Miyamoto R, Nakayama S, Mizuno K. Difficulty estimation of number place puzzle and its problem generation support. In: 2009 ICCAS-SICE; August 2009; Fukuoka, Japan. New York, NY, USA: IEEE. pp. 4542-4547.
5. Chmeit N. Using simulated annealing and ant-colony optimization algorithms to solve the scheduling problem. PhD Thesis, Notre Dame University-Louaize, Lebanon, 2012.
6. Chaitin GJ, Auslander MA, Chandra AK, Cocke J, Hopkins ME, Markstein PW. Register allocation via coloring. Comput Lang 1981; 6(1): 47-57.
7. Altunay H, Eren T. A literature review for course scheduling problem. Pamukkale Univ J Eng Sci 2017; 23(1): 55-70.
8. Appel K, Haken W. Every planar map is four colorable. In: Mathematical Solitaires and Games. New York, NY, USA: Routledge; 2019. pp. 145-152.

9. Saxena S, Thapar A, Bansal R. Total fuzzy graph coloring. J Hyperstructures 2022; 11(1): 84-108.
10. Cui G, Qin L, Liu S, Wang Y, Zhang X, Cao X. Modified PSO algorithm for solving planar graph coloring problem. Prog Nat Sci 2008; 18(3): 353-357.
11. Ahn S, Lee S, Chung TC. Modified ant colony system for coloring graphs. In: Fourth Int Conf Information, Communications and Signal Processing; 2003; Singapore. New York, NY, USA: IEEE.
12. Marappan R, Sethumadhavan G. Solution to graph coloring using genetic and tabu search procedures. Arab J Sci Eng 2018; 43(2): 525-542.
13. Ardelean SM, Udrescu M. Graph coloring using the reduced quantum genetic algorithm. PeerJ Comput Sci 2022; 8: e836.
14. Campbell C, Dahl E. QAOA of the highest order. In: 2022 IEEE 19th Int Conf Software Architecture Companion (ICSA-C); 2022; Montréal, Canada. New York, NY, USA: IEEE. pp. 141-146.
15. Karcı A, Yakut S, Öztemiz F. A new approach based on centrality value in solving the minimum vertex cover problem: Malatya centrality algorithm. Computer Science 2022.
16. Hong B. Generic algorithm of color planar graph. J Guizhou Univ (Nat Sci) 1999; 11(16): 232-297.
17. Zhao R ve diğerleri. Discrete selfish herd optimizer for solving graph coloring problem. Appl Intell 2020; 50(5): 1633-1656.
18. Hsu LY, Horng SJ, Fan P, Khan MK, Wang YR, Run RS, Chen RJ ve diğerleri. MTPSO algorithm for solving planar graph coloring problem. Expert Syst Appl 2011; 38(5): 5525-5531.
19. Zhao R, Wang Y, Liu C, Hu P, Jelodar H, Rabbani M, Li H. Discrete selfish herd optimizer for solving graph coloring problem. Appl Intell 2020; 50(5): 1633-1656.
20. Bui TN, Nguyen TH, Patel CM, Phan KAT. An ant-based algorithm for coloring graphs. Discrete Appl Math 2008; 156(2): 190-200.
21. Wang R, Zhou Y, Zhou Y, Bao Z. Local greedy flower pollination algorithm for solving planar graph coloring problem. J Comput Theor Nanosci 2015; 12(11): 4087-4096.
22. Surbakti NM, Ramadhani F. Implementation of the greedy algorithm for coloring graph based on four-color theorem. Sudo J Tek Inf 2022; 1(4): 178-182.
23. Luo Q. The 2nd Conference on Environmental Science and Information Application Technology: ESIAT 2010; July 17-18, 2010; Wuhan, China. New York, NY, USA: IEEE; 2010.
24. Tambouratzis T. A consensus-function artificial neural network for map-coloring. IEEE Trans Syst Man Cybern B Cybern 1998; 28(5): 721-728.
25. Talaván PM, Yáñez J. The graph coloring problem: A neuronal network approach. Eur J Oper Res 2008; 191(1): 100-111.