Single source multiroute flows and cuts on uniform capacity networks

0318590 - MÚ 2009 RIV US eng J - Článek v odborném periodiku
Bruhn, H. - Černý, J. - Hall, A. - Kolman, P. - Sgall, Jiří
Single source multiroute flows and cuts on uniform capacity networks.
[Multikomoditní toky a řezy v sítích s uniformní kapacitou a jedním zdrojem.]
Theory of Computing. Roč. 4, č. 1 (2008), s. 1-20. ISSN 1557-2862. E-ISSN 1557-2862
Grant CEP: GA ČR GA201/05/0124; GA AV ČR IAA1019401
Výzkumný záměr: CEZ:AV0Z10190503
Klíčová slova: graphs * multi-route flow * paths
Kód oboru RIV: BA - Obecná matematika

We study the relation between classical and multiroute single source flows on undirected networks with uniform capacities and we provide a tight bound.

Článek studuje aproximační algoritmy pro multikomoditní toky a řezy v sítích s uniformní kapacitou a jedním zdrojem
Trvalý link: http://hdl.handle.net/11104/0167962