Fleiner, Tamás (2014) On stable matchings and flows. ALGORITHMS, 7 (1). pp. 1-14. ISSN 1999-4893, ESSN: 1999-4893
|
Text
OnStableMatchings.pdf Download (236kB) | Preview |
Abstract
We describe a flow model related to ordinary network flows the same way as stable matchings are related to maximum matchings in bipartite graphs. We prove that there always exists a stable flow and generalize the lattice structure of stable marriages to stable flows. Our main tool is a straightforward reduction of the stable flow problem to stable allocations. For the sake of completeness, we prove the results we need on stable allocations as an application of Tarski's fixed point theorem. © 2014 by the authors.
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | Stable flows; Maximum matchings; Lattice structures; Fixed point theorems; Bipartite graphs; Stable marriages; stable allocations; network flows |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika > QA75 Electronic computers. Computer science / számítástechnika, számítógéptudomány |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 26 Jan 2015 12:40 |
| Last Modified: | 26 Jan 2015 12:40 |
| URI: | http://real.mtak.hu/id/eprint/20949 |
Actions (login required)
 |
Edit Item |
