TR-2012-13

Stable multicommodity flows

Tamás Király, Júlia Pap

Published in:
Algorithms 6:1 (2013), 161-168.



Abstract

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 path (with respect to a certain commodity) may include saturated arcs, provided that a positive amount of less preferred commodity is traded on the arc. We prove that a stable multicommodity flow always exists, although it is PPAD-hard to find one.
 

Previous version can be found here.


Bibtex entry:

@techreport{egres-12-13,
AUTHOR = {Kir{\'a}ly, Tam{\'a}s and Pap, J{\'u}lia},
TITLE = {Stable multicommodity flows},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2012},
NUMBER = {TR-2012-13}
}


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