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/