Discussiones Mathematicae Graph Theory 33(3) (2013) 559-569
doi: 10.7151/dmgt.1694

[BIBTex] [PDF] [PS]

Maximum semi-matching problem in bipartite graphs

Ján Katrenič and Gabriel Semanišin

Institute of Computer Science
P.J. Šafárik University, Faculty of Science
Jesenná 5, 041 54 Košice, Slovak Republic


An (f,g)-semi-matching in a bipartite graph G = (U ∪V,E) is a set of edges M ⊆ E such that each vertex u ∈ U is incident with at most f(u) edges of M, and each vertex v ∈ V is incident with at most g(v) edges of M. In this paper we give an algorithm that for a graph with n vertices and m edges, n ≤ m, constructs a maximum (f,g)-semi-matching in running time O(m·min{ √{ ∑u ∈ Uf(u)}, √{ ∑v ∈ Vg(v)}} ). Using the reduction of [5] our result on maximum (f,g)-semi-matching problem directly implies an algorithm for the optimal semi-matching problem with running time O( √nm logn).

Keywords: semi-matching, quasi-matching, bipartite graph, computational complexity

2010 Mathematics Subject Classification: 05C85, 05C70, 68Q17.


[1]P. Biró and E. McDermid, Matching with sizes (or scheduling with processing set restrictions), Electron. Notes Discrete Math. 36 (2010) 335--342, doi: 10.1016/j.endm.2010.05.043.
[2]D. Bokal, B. Brešar and J. Jerebic, A generalization of Hungarian method and Hall's theorem with applications in wireless sensor networks, Discrete Appl. Math. 160 (2012) 460--470, doi: 10.1016/j.dam.2011.11.007.
[3]J. Bruno, E.G. Coffman, Jr. and R. Sethi, Scheduling independent tasks to reduce mean finishing time, Commun. ACM 17 (1974) 382--387, doi: 10.1145/361011.361064.
[4]J. Fakcha
[5]F. Galčík, J. Katrenič, and G. Semanišin, On computing an optimal semi-matching, in: WG 2011, Lecture Notes in Comput. Sci. 6986, , ed(s), P. Kolman and J. Kratochvíl Springer, 2011) 250--261.
[6]T. Gu, L. Chang, and Z. Xu, A novel symbolic algorithm for maximum weighted matching in bipartite graphs, IJCNS 4 (2011) 111--121, doi: 10.4236/ijcns.2011.42014.
[7]N.J.A. Harvey, R.E. Ladner, L. Lovász, and T. Tamir, Semi-matchings for bipartite graphs and load balancing, J. Algorithms 59 (2006) 53--78, doi: 10.1016/j.jalgor.2005.01.003.
[8]J.E. Hopcroft and R.M. Karp, An n5/2algorithm for maximum matchings in bipartite graphs, SIAM J. Comput. 2 (1973) 225--231, doi: 10.1137/0202019.
[9]W.A. Horn, Minimizing average flow time with parallel machines, Oper. Res. 21 (1973) 846--847, doi: 10.1287/opre.21.3.846.
[10]S. Kravchenko and F. Werner, Parallel machine problems with equal processing times: a survey, J. Sched. 14 (2011) 435--444, doi: 10.1007/s10951-011-0231-3 .
[11]K. Lee, J. Leung, and M. Pinedo, Scheduling jobs with equal processing times subject to machine eligibility constraints, J. Sched. 14 (2011) 27--38, doi: 10.1007/s10951-010-0190-0.
[12]K. Lee, J.Y.T. Leung and M. Pinedo, A note on ``an approximation algorithm for the load-balanced semi-matching problem in weighted bipartite graphs``, Inform. Process. Lett. 109 (2009) 608--610, doi: 10.1016/j.ipl.2009.02.010.
[13]D. Luo, X. Zhu, X. Wu, and G. Chen, Maximizing lifetime for the shortest path aggregation tree in wireless sensor networks, in: INFOCOM 2011, ed(s), K. Gopalan and A.D. Striegel IEEE, 2011) 1566--1574.
[14]R. Machado and S. Tekinay, A survey of game-theoretic approaches in wireless sensor networks, Computer Networks 52 (2008) 3047--3061, doi: 10.1016/j.gaceta.2008.07.003.
[15]B. Malhotra, I. Nikolaidis, and M.A. Nascimento, Aggregation convergecast scheduling in wireless sensor networks, Wirel. Netw. 17 (2011) 319--335, doi: 10.1007/s11276-010-0282-y.
[16]M. Mucha and P. Sankowski, Maximum matchings via gaussian elimination, in: FOCS 2004, ed(s), E. Upfal IEEE Computer Society, 2004) 248--255.
[17]N. Sadagopan, M. Singh, and B. Krishnamachari, Decentralized utility-based sensor network design, Mobile Networks and Applications 11 (2006) 341--350, doi: 10.1007/s11036-006-5187-8.
[18]L.-H. Su., Scheduling on identical parallel machines to minimize total completion time with deadline and machine eligibility constraints, The International Journal of Advanced Manufacturing Technology 40 (2009) 572--581, doi: 10.1007/s00170-007-1369-1.
[19]H. Yuta, O. Hirotaka, S. Kunihiko, and Y. Masafumi, Optimal balanced semi-matchings for weighted bipartite graphs, IPSJ Digital Courier 3 (2007) 693--702, doi: 10.2197/ipsjdc.3.693.

Received 2 February 2012
Revised 25 June 2012
Accepted 25 June 2012