Perfectly matchable subgraph problem on a bipartite graph
RAIRO - Operations Research - Recherche Opérationnelle, Tome 44 (2010) no. 1, pp. 27-42.

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.

DOI : 10.1051/ro/2010004
Classification : 05C70, 05C85
Mots-clés : bipartite graph, extended polymatroid, perfect matching, perfectly matchable subgraph 
@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://www.numdam.org/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://www.numdam.org/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://www.numdam.org/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. http://www.numdam.org/articles/10.1051/ro/2010004/

[1] R. Ahuja, T.K. Magnanti and J.B. Orlin, Network Flows, Theory, Algorithms and Applications. Prentice-Hall (1993). | Zbl

[2] H. Alt, N. Blum, K. Mehlhorn and M. Paul, Computing maximum cardinality matching in time O(n 1.5 m/log|V|). Infor. Process. Lett. 37 (1991) 237-240. | Zbl

[3] E. Balas and W. Pulleyblank, The perfectly matchable subgraph polytope of a bipartite graph. Networks 13 (1983) 495-516. | Zbl

[4] E. Balas and W. Pulleyblank, The perfectly matchable subgraph polytope of an arbitrary graph. Combinatorica 9 (1989) 321-337. | Zbl

[5] M. L. Balinski, Signature methods for the assignment problem. Oper. Res. 33 (1985) 527-536. | Zbl

[6] D. Cornaz and A.R. Mahjoub, The Maximum Induced Bipartite Subgraph Problem with Edge Weight. SIAM J. Discrete Math. 3 (2007) 662-675. | Zbl

[7] W.H. Cunningham and J. Green-Krotki, A separation algorithm for matchable set polytope. Math. Program. 65 (1994) 139-150. | Zbl

[8] M. Grotschel, L. Lovasz and A. Schrijver, Geometric algorithms and combinatorial optimization. Springer-Verlag, Berlin (1988). | Zbl

[9] F.A. Sharifov, Determination of the minimum cut using the base of an extended polymatroid. Cybern. Syst. Anal. 6 (1997) 856-867 (translated from Kibernetika i Systemnyi Analis 6 (1996) 138-152, in Russian). | Zbl

Cité par Sources :