Maximum Semi-Matching Problem in Bipartite Graphs

Ján Katrenič; Gabriel Semanišin

Discussiones Mathematicae Graph Theory (2013)

  • Volume: 33, Issue: 3, page 559-569
  • ISSN: 2083-5892

Abstract

top
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).

How to cite

top

Ján Katrenič, and Gabriel Semanišin. "Maximum Semi-Matching Problem in Bipartite Graphs." Discussiones Mathematicae Graph Theory 33.3 (2013): 559-569. <http://eudml.org/doc/267689>.

@article{JánKatrenič2013,
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 [...] ) 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).},
author = {Ján Katrenič, Gabriel Semanišin},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {semi-matching; quasi-matching; bipartite graph; computational complexity},
language = {eng},
number = {3},
pages = {559-569},
title = {Maximum Semi-Matching Problem in Bipartite Graphs},
url = {http://eudml.org/doc/267689},
volume = {33},
year = {2013},
}

TY - JOUR
AU - Ján Katrenič
AU - Gabriel Semanišin
TI - Maximum Semi-Matching Problem in Bipartite Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2013
VL - 33
IS - 3
SP - 559
EP - 569
AB - 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).
LA - eng
KW - semi-matching; quasi-matching; bipartite graph; computational complexity
UR - http://eudml.org/doc/267689
ER -

References

top
  1. [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] Zbl1237.90083
  2. [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] Zbl1237.05159
  3. [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] Zbl0283.68039
  4. [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] Zbl1287.05148
  5. [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] Zbl05988783
  6. [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. [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] Zbl1100.68079
  8. [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. [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] Zbl0259.90030
  10. [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] Zbl1280.90058
  11. [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] Zbl1208.90071
  12. [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] Zbl1217.05187
  13. [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. [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] Zbl1152.68356
  15. [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. [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] Zbl1111.05304
  17. [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. [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. [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] 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.