Perfect Matching and Polymatroids
| Autor: | F. A. Sharifov |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Factor-critical graph
Discrete mathematics 0209 industrial biotechnology 021103 operations research General Computer Science 0211 other engineering and technologies 02 engineering and technology Combinatorics 020901 industrial engineering & automation Trivially perfect graph Perfect graph 3-dimensional matching Bipartite graph Perfect graph theorem Polymatroid Graph factorization Mathematics |
| Zdroj: | Cybernetics and Systems Analysis. 53:753-758 |
| ISSN: | 1573-8337 1060-0396 |
| DOI: | 10.1007/s10559-017-9977-8 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink