Hostname: page-component-7bb8b95d7b-wpx69 Total loading time: 0 Render date: 2024-09-20T17:21:04.045Z Has data issue: false hasContentIssue false
  • English
  • Français

Perfectly matchable subgraph problem on a bipartite graph

Published online by Cambridge University Press:  08 February 2010

Firdovsi Sharifov
Firdovsi Sharifov*
Affiliation:
Glushkov Institute of Cybernetics, Glushkova pr. 40, MSP, 252650 Kyiv, Ukraine; [email protected]
Get access

Abstract

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.

Keywords

Bipartite graphextended polymatroidperfect matchingperfectly matchable subgraph
Type
Research Article
Information
RAIRO - Operations Research , Volume 44 , Issue 1 , January 2010 , pp. 27 - 42
Copyright
© EDP Sciences, ROADEF, SMAI, 2010

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

R. Ahuja, T.K. Magnanti and J.B. Orlin, Network Flows, Theory, Algorithms and Applications. Prentice-Hall (1993).
Alt, H., Blum, N., Mehlhorn, K. and Paul, M., Computing maximum cardinality matching in time $O(n^{1.5}\sqrt{m/\log|V|})$ . Infor. Process. Lett. 37 (1991) 237–240. CrossRef
Balas, E. and Pulleyblank, W., The perfectly matchable subgraph polytope of a bipartite graph. Networks 13 (1983) 495–516. CrossRef
Balas, E. and Pulleyblank, W., The perfectly matchable subgraph polytope of an arbitrary graph. Combinatorica 9 (1989) 321–337. CrossRef
Balinski, M. L., Signature methods for the assignment problem. Oper. Res. 33 (1985) 527–536. CrossRef
Cornaz, D. and Mahjoub, A.R., The Maximum Induced Bipartite Subgraph Problem with Edge Weight. SIAM J. Discrete Math. 3 (2007) 662–675. CrossRef
Cunningham, W.H. and Green-Krotki, J., A separation algorithm for matchable set polytope. Math. Program. 65 (1994) 139–150. CrossRef
M. Grotschel, L. Lovasz and A. Schrijver, Geometric algorithms and combinatorial optimization. Springer-Verlag, Berlin (1988).
Sharifov, F.A., 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).