Academic Journals Database
Disseminating quality controlled scientific knowledge

Stable Multicommodity Flows

Author(s): Tamás Király | Júlia Pap

Journal: Algorithms
ISSN 1999-4893

Volume: 6;
Issue: 1;
Start page: 161;
Date: 2013;
Original page

Keywords: stable matching problem | stable flows | multicommodity flows | PPAD-completeness | Sperner’s Lemma

We extend the stable flow model of Fleiner to multicommodity flows. In addition to the preference lists of agents on trading partners for each commodity, every trading pair has a preference list on the commodities that the seller can sell to the buyer. A blocking walk (with respect to a certain commodity) may include saturated arcs, provided that a positive amount of less preferred commodity is traded along the arc. We prove that a stable multicommodity flow always exists, although it is PPAD-hard to find one.
RPA Switzerland

RPA Switzerland

Robotic process automation


Tango Jona
Tangokurs Rapperswil-Jona