IMPLEMENTATION OF GRAPH COLORING IN UMMUL MUKMININ HIGH SCHOOL STUDENT'S DORMITORY USING WELCH-POWELL ALGORITHM
Abstract
In Graph Theory, the concept of vertex coloring is an interesting topic because it can be implemented in various fields in everyday life. One of them is the distribution of dorm rooms at a school in Makassar. The placement of dorm rooms is made so that no students from the same class or region are in the same room. The data of region and class will be represented in an adjacency matrix with 137 rows and columns. Furthermore, the coloring will be solved by using the Welch-Powell algorithm. The coloring results obtained were 50 colors. That means, the rooms needed to place 137 students so that no one comes from the same region, and classes are 50 rooms with a maximum capacity of 4 people in each room.
Downloads
References
R. Balakrishnan and K. Ranganathan, A Textbook of Graph Theory. New York, NY: Springer New York, 2012. doi: 10.1007/978-1-4614-4529-6.
S. E. Irwan, “Aplikasi Pewarnaan Graf pada Penempatan Kamar Mahasiswa (Studi Kasus: Asrama Institut Teknologi Sumatera),” Sainmatika: Jurnal Ilmiah Matematika dan Ilmu Pengetahuan Alam, vol. 17, no. 1, p. 17, Apr. 2020, doi: 10.31851/sainmatika.v17i1.3137.
A. M. Soimah and N. S. M. Mussafi, “Pewarnaan Simpul dengan Algoritma Welch-Powell pada Traffic Light di YOGYAKARTA,” Jurnal Fourier, vol. 2, no. 2, pp. 73–79, 2013.
L. S. Lestari and K. Kunci, “PENERAPAN ALGORITMA WELCH-POWELL PADA PEWARNAAN GRAF DALAM PEMETAAN WILAYAH DI KOTA MEDAN,” 2020.
Hasmawati, Pengantar dan Jenis-jenis Graf. Makassar: unhas press, 2020.
G. Chartrand, L. Lesniak, and P. Zhang, Graphs & Digraphs. Chapman and Hall/CRC, 2015. doi: 10.1201/b19731.
H. Lu, M. Halappanavar, D. Chavarria-Miranda, A. H. Gebremedhin, A. Panyala, and A. Kalyanaraman, “Algorithms for Balanced Graph Colorings with Applications in Parallel Computing,” IEEE Transactions on Parallel and Distributed Systems, vol. 28, no. 5, pp. 1240–1256, May 2017, doi: 10.1109/TPDS.2016.2620142.
M. ASLAN, “A Performance Comparison of Graph Coloring Algorithms,” International Journal of Intelligent Systems and Applications in Engineering, vol. 4, no. Special Issue-1, pp. 1–7, Dec. 2016, doi: 10.18201/ijisae.273053.
S. Thadani, S. Bagora, and A. Sharma, “Applications of graph coloring in various fields,” Mater Today Proc, vol. 66, pp. 3498–3501, 2022, doi: 10.1016/j.matpr.2022.06.392.
T. Park and C. Y. Lee, “APPLICATION OF THE GRAPH COLORING ALGORITHM TO THE FREQUENCY ASSIGNMENT PROBLEM,” Journal of the Operations Research Society of Japan, vol. 39, no. 2, pp. 258–265, 1996, doi: 10.15807/jorsj.39.258.
M. Demange, T. Ekim, B. Ries, and C. Tanasescu, “On some applications of the selective graph coloring problem,” Eur J Oper Res, vol. 240, no. 2, pp. 307–314, Jan. 2015, doi: 10.1016/j.ejor.2014.05.011.
Y. V. Ermanto and Y. Finsensia Riti, “Perbandingan Implementasi Algoritma Welch-Powell Dan Recursive Largest First Dalam Penjadwalan Mata Kuliah,” Jurnal Teknologi Dan Sistem Informasi Bisnis, vol. 4, no. 1, pp. 204–212, Jan. 2022, doi: 10.47233/jteksis.v4i1.402.
D. Abdullah et al., “Lecture Scheduling System Using Welch Powell Graph Coloring Algorithm in Informatics Engineering Departement of Universitas Malikussaleh,” J Phys Conf Ser, vol. 1363, no. 1, p. 012074, Nov. 2019, doi: 10.1088/1742-6596/1363/1/012074.
R. Diestel, Graph Theory: 5th edition, 5th ed. Springer-Verlag, 2016.
G. Chartrand and P. Zhang, Chromatic Graph Theory. USA: Chapman and Hall/CRC, 2019. doi: 10.1201/9780429438868.
J. A. Bondy and U. S. R. Murty, Graph Theory, vol. 244. London: Springer London, 2008. doi: 10.1007/978-1-84628-970-5.
Copyright (c) 2023 Nur Rohmah Oktaviani Putri, Edy Saputra, Andi Anita Lisnasari
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Authors who publish with this Journal agree to the following terms:
- Author retain copyright and grant the journal right of first publication with the work simultaneously licensed under a creative commons attribution license that allow others to share the work within an acknowledgement of the work’s authorship and initial publication of this journal.
- Authors are able to enter into separate, additional contractual arrangement for the non-exclusive distribution of the journal’s published version of the work (e.g. acknowledgement of its initial publication in this journal).
- Authors are permitted and encouraged to post their work online (e.g. in institutional repositories or on their websites) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published works.
