An Application for Weighted Graph Matching in Job Assignment Problems
Article Sidebar
Main Article Content
Abstract
This research primarily aims to design and develop an application for finding optimal matchings in weighted graphs to address assignment problems, along with developing matching algorithms that cover five key characteristics to enhance flexibility in selecting appropriate solutions across diverse contexts. Furthermore, it aims to analyze and verify the structural properties of graphs, specifically regarding bipartite graph detection and the existence of perfect matchings. The application was developed using the Python programming language and tested through five simulated case studies involving various assignment problems. The research instruments consist of the developed application for optimal matching in weighted graphs and an algorithm validation record. The statistical analysis involves calculating the percentage of accuracy and comparing the results with known optimal solutions. The results indicate that the developed application successfully identifies optimal matchings in weighted graphs across all five characteristics: (1) maximum matching with the highest total weight, (2) maximum matching with the lowest total weight, (3) matching with the highest total weight, (4) matching with the lowest total weight, and (5) maximum matching regardless of total weight. By clearly defining the application's goals and the scope of weighted graph matching, the system facilitates efficient assignment problem-solving with greater flexibility compared to typical applications. Moreover, the system accurately verifies bipartite graph properties and the existence of perfect matchings, thereby reducing complexity in graph analysis and serving as an effective decision-support tool for both academic and business planning purposes.
Downloads
Article Details
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
The owner (Research and Development Institute, Kalasin University), the authors agree that any copies of the article or any part thereof distributed or posted by them in print or electronic format as permitted will include the notice of copyright as stipulated in the journal and a full citation to the final published version of the contribution in the journal as published by Research and Development Institute, Kalasin University.
References
Shahriar Tanvir Alam, Eshfar Sagor, Tanjeel Ahmed, Tabassum Haque, Md Shoaib Mahmud, Salman Ibrahim, Ononya Shahjahan, Mubtasim Rubaet. Assessment of Assignment Problem using Hungarian Method. Proceedings of the First Australian International Conference on Industrial Engineering and Operations Management; 20-21 December 2022; Sydney, Australia. 2328-2338. https://ieomsociety.org/proceedings/2022australia/498.pdf
Jayasree T G , Malavika V. Graph Theory for Optimum Assignment. International Journal of Scientific Research in Science and Technology. 2025; 12(16): 337-343. https://ijsrst.com/home/issue/view/article.php?id=IJSRST25121640
Fatemeh Rajabi-Alni, Alireza Bagheri. Computing a Many-to-Many Matching with Demands and Capacities between Two Sets Using the Hungarian Algorithm. Journal of Mathematics. 2023; Volume 2023, Article ID 7761902: 1-6. https://doi.org/10.1155/2023/7761902
M. Usha Devi, A. Marimuthu, S. Santhana Megala. Bipartite Graph Matching in Donor-Recipient Using Enhanced Hopcroft Karp Algorithm for Liver transplantation. Advances and Applications in Mathematical Sciences. 2022; 21(9): 5291-5298.
Gabriel Cristian Dragomir-Loga, Marius Pop. Edmonds’ Blossom Algorithm Analysis in a Medical Emergency Management System. The 9th IEEE International Conference on E-Health and Bioengineering - EHB 2021 Grigore T. Popa University of Medicine and Pharmacy; 18-19 November 2021; Web Conference, Romania. 1-4. https://ieeexplore.ieee.org/document/9657586
นวรัตน์ อนันต์ชื่น. ทฤษฎีกราฟ 1 .พิมพ์ครั้งที่ 1. นครปฐม: ภาควิชาคณิตศาสตร์ คณะวิทยาศาสตร์ มหาวิทยาลัยศิลปากร; 2540. 5-7, 113-118. https://lib.rmutp.ac.th/bibitem?bibid=b00033744
Chartrand, G. and Lesniak, L. Graphs & Digraphs. 4th ed. Florida: Chapman & Hall/CRC; 2005. 28-30. https://books.google.co.th/books/about/Graphs_Digraphs_Fourth_Edition.html?id=LgZKLPRH2D4C&redir_esc=y
วรานุช แขมมณี. ทฤษฎีกราฟเบื้องต้น. พิมพ์ครั้งที่ 1. สำนักพิมพ์แห่งจุฬาลงกรณ์มหาวิทยาลัย; 2559. 2-6, 120. https://www.chulabook.com/testprep/25508?srsltid=AfmBOoq4WHZqXg8sjDXafxZywmtLfRs1QrJqnoZBuAAcf2t2OETPgZgC
West, D.B. Introduction to Graph Theory. 2nd ed. New Jersey: Prentice Hall; 2001. 107-111. https://books.google.co.th/books/about/Introduction_to_Graph_Theory.html?id=TuvuAAAAMAAJ&redir_esc=y
Bondy, AJ and Murty, USR. Graph Theory with Applications. 5th ed. U.S.A: Elsevier Science Publishing Co., Inc.; 1982. 70-90. https://www.iro.umontreal.ca/~hahn/IFT3545/GTWA.pdf
วิษณุ ช้างเนียม. โครงสร้างข้อมูลและอัลกอริทึม + การประยุกต์ใช้ AI (DATA STRUCTURE & ALGORITHM + AI). พิมพ์ครั้งที่ 3 นนทบุรี: บริษัท ไอดีซี พรีเมียร์ จำกัด; 2568. 305-307. https://www.chulabook.com/computer/219458?srsltid=AfmBOopXXwwLjJGsVu32jHSVbHkWBe-arLZFB_adImKtsZnlPnrcgBNc
Akshitha, S., Ananda Kumar, K. S., Nethritha Meda, M., Sowmva, R. and Suman Pawar, R. Implementation of Hungarian Algorithm to obtain Optimal Solution for Travelling Salesman Problem. In: 3rd IEEE. https://ieeexplore.ieee.org/document/9012439
Wang, Y., Wu, Y. -X. and Zhang, H. An Improved Multi-Robot Task Allocation Algorithm Based on the Hungarian Algorithm. In: 44th Chinese Control Conference (CCC); 28-30 July 2025; Chongqing, China. 4903-4908. https://ieeexplore.ieee.org/document/11178894
Othman, F., Abdullah, R. and Salam, R. A. Bipartite Graph for Protein Structure Matching, In: Second Asia International Conference on Modelling & Simulation (AMS); 13-15 May 2008; Kuala Lumpur, Malaysia. IEEE publisher; 928-933https://ieeexplore.ieee.org/document/4530600
Rong, H. -g., Li, Y. -j. and Zhang, X. -s. An Image Matching Algorithm Based on Bipartite Graph, In: 7th International Conference on Information Science, Computer Technology and Transportation; 27-29 May 2022; Xishuangbanna, China. 1-4. https://ieeexplore.ieee.org/abstract/document/10071784
A. B. Chaudhuri. Flowchart and Algorithm Basics The Art of Programming. 2nd ed. Virginia: Mercury Learning and Information.; 2020. 1-17. https://books.google.co.th/books/about/Flowchart_and_Algorithm_Basics.html?id=pUOQzQEACAAJ&redir_esc=y
ศิริพร อ่วมมีเพียร. วิชาการเขียนโปรแกรมคอมพิวเตอร์เบื้องต้นรหัสวิชา 20901-1002. พิมพ์ครั้งที่ 1. กรุงเทพฯ : วังอักษร, 2563. 21-38. https://search-library.spu.ac.th/bib/189590
Shopov, V. and Markova, V. Application of Hungarian Algorithm for Assignment Problem. In: 2021 International Conference on Information Technologies (InfoTech); 16-17 Sep 2021; Varna, Bulgaria. Piscataway: Institute of Electrical and Electronics Engineers, Inc.; 2021. 1–4. https://ieeexplore.ieee.org/abstract/document/9548600
Deo, N. Graph Theory with Applications to Engineering and Computer Science. 2nd ed. New York: Dover Publications, Inc.; 2016. 496. https://books.google.co.th/books/about/Graph_Theory_with_Applications_to_Engine.html?id=uk1KDAAAQBAJ&redir_esc=y
Denise, G. and Matthias, B. The Practitioner's Guide to Graph Data. 1sted. California: O'Reilly Media.; 2020. 420. https://books.google.co.th/books/about/The_Practitioner_s_Guide_to_Graph_Data.html?id=n6nYDwAAQBAJ&redir_esc=y
