REAL

On stable matchings and flows

Fleiner, Tamás (2014) On stable matchings and flows. ALGORITHMS, 7 (1). pp. 1-14. ISSN 1999-4893, ESSN: 1999-4893

[img]
Preview
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 Edit Item