Matching on Bipartite Graphs with Applications to School Course Registration Systems

Authors: Zhihan Li

Abstract:

Nowadays, most universities use the course enrollment system considering students’ registration orders. However, the students’ preference level to certain courses is also one important factor to consider. In this research, the possibility of applying a preference-first system has been discussed and analyzed compared to the order-first system. A bipartite graph is applied to resemble the relationship between students and courses they tend to register. With the graph set up, we apply Ford-Fulkerson (F.F.) Algorithm to maximize parings between two sets of nodes, in our case, students and courses. Two models are proposed in this paper: the one considered students’ order first, and the one considered students’ preference first. By comparing and contrasting the two models, we highlight the usability of models which potentially leads to better designs for school course registration systems.

Keywords: Bipartite graph, Ford-Fulkerson Algorithm, graph theory, maximum matching.

References:

[1] Marwan Abboud, Lina Mariya Abou Jaoude, and Ziad Kerbage.“ Real Time GPS Navigation System ”, Available: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.560.3002&rep=rep1&type=pdf
[2] Zhu, Zhiguo, et al. “Measuring Influence in Online Social Network Based on the User-Content Bipartite Graph.” Computers in Human Behavior, vol. 52, 2015, p. 184.
[3] Asratian, Armen S., et al. Bipartite Graphs and Their Applications. 1998.
[4] Strang, Gilbert. Linear Algebra and Its Applications. 3rd ed., Harcourt, Brace, Jovanovich, Pulishers, 1988.
[5] Weisstein, Eric W. “Weighted Graph”. From MathWorld—A Wolfram Web Resource. https://mathworld.wolfram.com/WeightedGraph.html
[6] Gibbons, Alan. Algorithmic Graph Theory. Cambridge University Press, 1985.
[7] Ford, L. R, and Fulkerson, D. R. “Maximal Flow through a Network.” Canadian Journal of Mathematics, vol. 8, 2018, pp. 399–404.
[8] Adamidis, Panagiotis, and Kynigopoulos, Georgios. “EvoWebReg.” International Journal of Operations Research and Information Systems, vol. 5, no. 1, 2014, pp. 1–18.