Perfectly matchable subgraph problem on a bipartite graph

Perfectly matchable subgraph problem on a bipartite graph

0.00 Avg rating0 Votes
Article ID: iaor20101890
Volume: 44
Issue: 1
Start Page Number: 27
End Page Number: 42
Publication Date: Jan 2010
Journal: RAIRO Operations Research
Authors:
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.

Reviews

Required fields are marked *. Your email address will not be published.