Voir la notice de l'article provenant de la source Numdam
We consider the maximum weight perfectly matchable subgraph problem on a bipartite graph G=(UV,E) with respect to given nonnegative weights of its edges. We show that G has a perfect matching if and only if some vector indexed by the nodes in UV is a base of an extended polymatroid associated with a submodular function defined on the subsets of UV. The dual problem of the separation problem for the extended polymatroid is transformed to the special maximum flow problem on G. In this paper, we give a linear programming formulation for the maximum weight perfectly matchable subgraph problem and propose an O(n3) algorithm to solve it.
@article{RO_2010__44_1_27_0,
author = {Sharifov, Firdovsi},
title = {Perfectly matchable subgraph problem on a bipartite graph},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {27--42},
publisher = {EDP-Sciences},
volume = {44},
number = {1},
year = {2010},
doi = {10.1051/ro/2010004},
mrnumber = {2642914},
zbl = {1218.05149},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ro/2010004/}
}
TY - JOUR AU - Sharifov, Firdovsi TI - Perfectly matchable subgraph problem on a bipartite graph JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2010 SP - 27 EP - 42 VL - 44 IS - 1 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ro/2010004/ DO - 10.1051/ro/2010004 LA - en ID - RO_2010__44_1_27_0 ER -
%0 Journal Article %A Sharifov, Firdovsi %T Perfectly matchable subgraph problem on a bipartite graph %J RAIRO - Operations Research - Recherche Opérationnelle %D 2010 %P 27-42 %V 44 %N 1 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ro/2010004/ %R 10.1051/ro/2010004 %G en %F RO_2010__44_1_27_0
Sharifov, Firdovsi. Perfectly matchable subgraph problem on a bipartite graph. RAIRO - Operations Research - Recherche Opérationnelle, Tome 44 (2010) no. 1, pp. 27-42. doi: 10.1051/ro/2010004
Cité par Sources :