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

Voir la notice de l'article dans European Digital Mathematics Library

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).
Classification : 68Q17, 05C70, 05C85
Mots-clés : semi-matching, quasi-matching, bipartite graph, computational complexity 
@article{DMGT_2013__33_3_267689,
     author = {J\'an Katreni\v{c} and Gabriel Semani\v{s}in},
     title = {Maximum {Semi-Matching} {Problem} in {Bipartite} {Graphs}},
     journal = {Discussiones Mathematicae Graph Theory},
     pages = {559},
     publisher = {mathdoc},
     volume = {33},
     number = {3},
     year = {2013},
     zbl = {1275.05045},
     language = {en},
     url = {https://geodesic-test.mathdoc.fr/item/DMGT_2013__33_3_267689/}
}
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
SP  - 559
VL  - 33
IS  - 3
PB  - mathdoc
UR  - https://geodesic-test.mathdoc.fr/item/DMGT_2013__33_3_267689/
LA  - en
ID  - DMGT_2013__33_3_267689
ER  - 
%0 Journal Article
%A Ján Katrenič
%A Gabriel Semanišin
%T Maximum Semi-Matching Problem in Bipartite Graphs
%J Discussiones Mathematicae Graph Theory
%D 2013
%P 559
%V 33
%N 3
%I mathdoc
%U https://geodesic-test.mathdoc.fr/item/DMGT_2013__33_3_267689/
%G en
%F DMGT_2013__33_3_267689
Ján Katrenič; Gabriel Semanišin. Maximum Semi-Matching Problem in Bipartite Graphs. Discussiones Mathematicae Graph Theory, Tome 33 (2013) no. 3, p. 559. https://geodesic-test.mathdoc.fr/item/DMGT_2013__33_3_267689/