PDF
Discussiones Mathematicae Graph Theory 33(3) (2013)
559-569
DOI: https://doi.org/10.7151/dmgt.1694
Maximum semi-matching problem in bipartite graphs
| Ján Katrenič and Gabriel Semanišin
Institute of Computer Science |
Abstract
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.
References
| [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
Close