Perfectly matchable subgraph problem on a bipartite graph

Firdovsi Sharifov

RAIRO - Operations Research (2010)

  • Volume: 44, Issue: 1, page 27-42
  • ISSN: 0399-0559

Abstract

top
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.

How to cite

top

Sharifov, Firdovsi. "Perfectly matchable subgraph problem on a bipartite graph." RAIRO - Operations Research 44.1 (2010): 27-42. <http://eudml.org/doc/250823>.

@article{Sharifov2010,
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. },
author = {Sharifov, Firdovsi},
journal = {RAIRO - Operations Research},
keywords = {Bipartite graph; extended polymatroid; perfect matching; perfectly matchable subgraph; bipartite graph; perfectly matchable subgraph},
language = {eng},
month = {2},
number = {1},
pages = {27-42},
publisher = {EDP Sciences},
title = {Perfectly matchable subgraph problem on a bipartite graph},
url = {http://eudml.org/doc/250823},
volume = {44},
year = {2010},
}

TY - JOUR
AU - Sharifov, Firdovsi
TI - Perfectly matchable subgraph problem on a bipartite graph
JO - RAIRO - Operations Research
DA - 2010/2//
PB - EDP Sciences
VL - 44
IS - 1
SP - 27
EP - 42
AB - 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.
LA - eng
KW - Bipartite graph; extended polymatroid; perfect matching; perfectly matchable subgraph; bipartite graph; perfectly matchable subgraph
UR - http://eudml.org/doc/250823
ER -

References

top
  1. R. Ahuja, T.K. Magnanti and J.B. Orlin, Network Flows, Theory, Algorithms and Applications. Prentice-Hall (1993).  Zbl1201.90001
  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.  Zbl0714.68036
  3. E. Balas and W. Pulleyblank, The perfectly matchable subgraph polytope of a bipartite graph. Networks13 (1983) 495–516.  Zbl0525.90069
  4. E. Balas and W. Pulleyblank, The perfectly matchable subgraph polytope of an arbitrary graph. Combinatorica9 (1989) 321–337.  Zbl0723.05087
  5. M. L. Balinski, Signature methods for the assignment problem. Oper. Res.33 (1985) 527–536.  Zbl0583.90064
  6. D. Cornaz and A.R. Mahjoub, The Maximum Induced Bipartite Subgraph Problem with Edge Weight. SIAM J. Discrete Math.3 (2007) 662–675.  Zbl1141.05076
  7. W.H. Cunningham and J. Green-Krotki, A separation algorithm for matchable set polytope. Math. Program.65 (1994) 139–150.  Zbl0819.90120
  8. M. Grotschel, L. Lovasz and A. Schrijver, Geometric algorithms and combinatorial optimization. Springer-Verlag, Berlin (1988).  Zbl0634.05001
  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 Analis6 (1996) 138–152, in Russian).  Zbl0892.90066

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.