Geodesic
Maximum Semi-Matching Problem in Bipartite Graphs
Discussiones Mathematicae. Graph Theory, Tome 33 (2013) no. 3, pp. 559-569.

Voir la notice de l'article provenant de la source Library of Science

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 ∈ U f(u)), √(Σ_v ∈ V g(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( √(n) m log n ).
Keywords: semi-matching, quasi-matching, bipartite graph, computational complexity 
@article{DMGT_2013_33_3_a5,
     author = {Katreni\v{c}, J\'an and Semani\v{s}in, Gabriel},
     title = {Maximum {Semi-Matching} {Problem} in {Bipartite} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {559--569},
     publisher = {mathdoc},
     volume = {33},
     number = {3},
     year = {2013},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2013_33_3_a5/}
}
TY  - JOUR
AU  - Katrenič, Ján
AU  - Semanišin, Gabriel
TI  - Maximum Semi-Matching Problem in Bipartite Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2013
SP  - 559
EP  - 569
VL  - 33
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2013_33_3_a5/
LA  - en
ID  - DMGT_2013_33_3_a5
ER  - 
%0 Journal Article
%A Katrenič, Ján
%A Semanišin, Gabriel
%T Maximum Semi-Matching Problem in Bipartite Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2013
%P 559-569
%V 33
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2013_33_3_a5/
%G en
%F DMGT_2013_33_3_a5
Katrenič, Ján; Semanišin, Gabriel. Maximum Semi-Matching Problem in Bipartite Graphs. Discussiones Mathematicae. Graph Theory, Tome 33 (2013) no. 3, pp. 559-569. http://geodesic.mathdoc.fr/item/DMGT_2013_33_3_a5/

[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. 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

[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

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

[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, E. Upfal (Ed(s)), (IEEE Computer Society, 2004) 248-255. doi:10.1109/FOCS.2004.40

[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 semimatchings for weighted bipartite graphs, IPSJ Digital Courier 3 (2007) 693-702. doi:10.2197/ipsjdc.3.693