Article contents
Perfectly matchable subgraph problem on a bipartite graph
Published online by Cambridge University Press: 08 February 2010
Abstract
We consider the maximum weight perfectly matchable subgraph problemon a bipartite graph G=(UV,E) with respect to given nonnegativeweights of its edges. We show that G has a perfect matching if andonly if some vector indexed by the nodes in UV is a base of anextended polymatroid associated with a submodular function definedon the subsets of UV. The dual problem of the separation problemfor the extended polymatroid is transformed to the special maximumflow problem on G. In this paper, we give a linear programmingformulation for the maximum weight perfectly matchable subgraphproblem and propose an O(n 3) algorithm to solve it.
- Type
- Research Article
- Information
- Copyright
- © EDP Sciences, ROADEF, SMAI, 2010
References
- 2
- Cited by