Maximum Semi-Matching Problem in Bipartite Graphs

Ján Katrenič ; Gabriel Semanišin

Discussiones Mathematicae Graph Theory, Tome 33 (2013), p. 559-569 / Harvested from The Polish Digital Mathematics Library

Résumé

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 [...] ) 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( [...] log n).

Détail

Publié le : 2013-01-01

Zbl 1275.05045

EUDML-ID : urn:eudml:doc:267689

Bibliographie

[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[Crossref] | Zbl 1237.90083

[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[Crossref][WoS] | Zbl 1237.05159

[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[Crossref] | Zbl 0283.68039

[4] J. Fakcharoenphol, B. Laekhanukit, and D. Nanongkai, Faster algorithms for semimatching problems, in: ICALP 2010, Lecture Notes in Comput. Sci. 6198, S. Abramsky, C. Gavoille, C. Kirchner, F. M. auf der Heide, P. G. Spirakis (Ed(s)), (Springer, 2010) 176-187. doi:10.1007/978-3-642-14165-2 16[Crossref] | Zbl 1287.05148

[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,, P. Kolman and J. Kratochv´ıl (Ed(s)), (Springer, 2011) 250-261. doi:10.1007/978-3-642-25870-1 23[Crossref] | Zbl 05988783

[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[Crossref]

[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[Crossref] | Zbl 1100.68079

[8] J.E. Hopcroft and R.M. Karp, An n5/2 algorithm for maximum matchings in bipartite graphs, SIAM J. Comput. 2 (1973) 225-231. doi:10.1137/0202019[Crossref]

[9] W.A. Horn, Minimizing average flow time with parallel machines, Oper. Res. 21 (1973) 846-847. doi:10.1287/opre.21.3.846[Crossref] | Zbl 0259.90030

[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[WoS][Crossref] | Zbl 1280.90058

[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[Crossref][WoS] | Zbl 1208.90071

[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[WoS][Crossref] | Zbl 1217.05187

[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, K. Gopalan and A.D. Striegel (Ed(s)), (IEEE, 2011) 1566-1574. doi:10.1109/INFCOM.2011.5934947[Crossref]

[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[Crossref] | Zbl 1152.68356

[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[Crossref]

[16] M. Mucha and P. Sankowski, Maximum matchings via gaussian elimination, in: FOCS 2004, E. Upfal (Ed(s)), (IEEE Computer Society, 2004) 248-255. doi:10.1109/FOCS.2004.40[Crossref] | Zbl 1111.05304

[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[Crossref]

[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[WoS][Crossref]

[19] H. Yuta, O. Hirotaka, S. Kunihiko, and Y. Masafumi, Optimal balanced semimatchings for weighted bipartite graphs, IPSJ Digital Courier 3 (2007) 693-702. doi:10.2197/ipsjdc.3.693 [Crossref]