Совершенные паросочетания и полиматроиды / Шарифов Ф. А. (2017)
Ukrainian

English  Cybernetics and Systems Analysis   /     Issue (2017, 53 (5))

Sharifov F.A.
Perfect matching and polymatroids

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. © 2017, Springer Science+Business Media, LLC.

Keywords: extended polymatroid, graph, perfect matching, Computer science, Cybernetics, graph, Perfect matchings, Polymatroids, Submodular functions, Vertex set, Flow graphs


Cite:
Sharifov F.A. (2017). Perfect matching and polymatroids. Cybernetics and Systems Analysis, 53 (5), 113-119. doi: https://doi.org/10.1007/s10559-017-9977-8 http://jnas.nbuv.gov.ua/article/UJRN-0000754489 [In Russian].


 

Інститут інформаційних технологій НБУВ


+38 (044) 525-36-24
Голосіївський просп., 3, к. 209
м. Київ, 03039, Україна