TR-2009-11

On stable matchings and flows

Tamás Fleiner



Abstract

We describe a flow model that generalizes ordinary network flows the same way as stable matchings generalize the bipartite matching problem. We prove that there always exists a stable flow, generalize the lattice structure of stable marriages to stable flows and prove a flow extension of Pym's linking theorem.


Bibtex entry:

@techreport{egres-09-11,
AUTHOR = {Fleiner, Tam{\'a}s},
TITLE = {On stable matchings and flows},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2009},
NUMBER = {TR-2009-11}
}


Last modification: 21.9.2017. Please email your comments to Tamás Király!