Back to Search
Start Over
Perfect Matching and Polymatroids
- Source :
- Cybernetics and Systems Analysis. 53:753-758
- Publication Year :
- 2017
- Publisher :
- Springer Science and Business Media LLC, 2017.
-
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.
- Subjects :
- 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
Subjects
Details
- ISSN :
- 15738337 and 10600396
- Volume :
- 53
- Database :
- OpenAIRE
- Journal :
- Cybernetics and Systems Analysis
- Accession number :
- edsair.doi...........af53374cb870a136203f9c6702b76549