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.