Commenced in January 2007
Frequency: Monthly
Edition: International
Paper Count: 31097
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: Graph Theory, bipartite graph, maximum matching, Ford-Fulkerson Algorithm

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 162

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.