PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2013 | 33 | 3 | 559-569
Tytuł artykułu

Maximum Semi-Matching Problem in Bipartite Graphs

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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).
Wydawca
Rocznik
Tom
33
Numer
3
Strony
559-569
Opis fizyczny
Daty
wydano
2013-07-01
online
2013-07-30
Twórcy
  • Institute of Computer Science, P.J. Šafárik University, Faculty of Science, Jesenná 5, 041 54 Košice, Slovak Republic, jan.katrenic@upjs.sk
  • Institute of Computer Science, P.J. Šafárik University, Faculty of Science, Jesenná 5, 041 54 Košice, Slovak Republic, e-mailgabriel.semanisin@upjs.sk
Bibliografia
  • [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]
  • [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]
  • [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]
  • [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]
  • [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]
  • [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]
  • [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]
  • [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]
  • [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]
  • [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]
  • [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]
  • [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]
  • [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]
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1694
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.