Perfect Matching and Polymatroids |
| |
| Authors: | F. A. Sharifov |
| |
| Affiliation: | 1.V. M. Glushkov Institute of Cybernetics,National Academy of Sciences of Ukraine,Kyiv,Ukraine |
| |
| Abstract: | It is shown that any graph has a perfect matching if and only if a specially defined vector is the base of extended polymatroid associated with submodular function defined on subsets of vertex set. Based on this fact, different algorithms for testing flow feasibility can be used to find some perfect matching in a given graph. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
