[ga.git] / 2-dinic / 2-dinic.tex

\input ../sgr.tex

\prednaska{2}{Dinicův algoritmus a jeho varianty}{}

Maximální tok v~síti už umíme najít pomocí Fordova-Fulkersonova algoritmu
z~minulé kapitoly. Nyní pojednáme o~efektivnějším Dinicově algoritmu
a o~různých jeho variantách pro sítě ve~speciálním tvaru.

\h{Dinicův algoritmus}

Dinicův algoritmus je založen na~následující myšlence: Ve~Fordově-Fulkersonově algoritmu
nemusíme přičítat jen zlepšující cesty, ale je možné přičítat rovnou zlepšující
toky. Nejlépe toky takové, aby je nebylo obtížné najít, a~přitom aby původní tok
dostatečně obohatily. Vhodnými objekty k~tomuto účelu jsou blokující toky:

\s{Definice:} {\I Blokující tok} je tok takový, že každá orientovaná $st$-cesta
obsahuje alespoň jednu nasycenou hranu. [Tj. takový tok, který by našel F-F algoritmus,
kdyby neuvažoval rezervy v~protisměru.]

\s{Algoritmus (Dinic):}

\algo
\:Začneme s~libovolným tokem~$f$, například prázdným (všude nulovým).
\:Iterativně vylepšujeme tok pomocí zlepšujících toků: {\I (vnější cyklus)}
\::Sestrojíme síť rezerv: vrcholy a hrany jsou tytéž, kapacity jsou určeny rezervami v~původní síti.
Dále budeme pracovat s~ní.
\::Najdeme nejkratší $st$-cestu. Když žádná neexistuje, skončíme.
\::Pročistíme síť, tj. ponecháme v ní pouze vrcholy a hrany na nejkratších $st$-cestách.
\::Najdeme v~pročištěné síti blokující tok $f_B$:
\:::$f_B \leftarrow \<prázdný tok>$
\:::Postupně přidáváme $st$-cesty: {\I (vnitřní cyklus)}
\::::Najdeme $st$-cestu. Např. hladově -- \uv{rovnou za nosem}.
\::::Pošleme co nejvíce po~nalezené cestě.
\::::Smažeme nasycené hrany. (Pozor, smazáním hran mohou vzniknout slepé uličky,
čímž se znečistí síť a nebude fungovat hladové hledání cest.)
\::::Dočistíme síť.
\::Zlepšíme $f$ podle $f_B$
\endalgo

\finalfix{\vskip-3pt}
\figure{dinic-cistasit.eps}{Pročištěná síť rozdělená do vrstev}{0.4\hsize}
\finalfix{\vskip-6pt}

\s{Složitost algoritmu:}
Označme $l$ délku nejkratší $st$-cesty, $n$ počet vrcholů sítě a $m$ počet hran sítě.

\itemize\ibull
\:Jeden průchod vnitřním cyklem trvá $\O(l)$, což můžeme odhadnout jako $\O(n)$, protože vždy platí $l \leq n$.
\:Vnitřní cyklus se provede maximálně $m$-krát, protože se vždy alespoň jedna hrana nasytí
  a ze sítě vypadne, takže krok~6 mimo podkroku~12 bude trvat $\O(mn)$.
\:Čištění a dočišťování sítě dohromady provedeme takto:
  \itemize\ibull
  \:Rozvrstvíme vrcholy podle vzdálenosti od $s$.
  \:Zařízneme dlouhé cesty (delší, než do vrstvy obsahující $t$).
  \:Držíme si frontu vrcholů, které mají $\deg^+ = 0$ či $\deg^- = 0$.
  \:Vrcholy z~fronty vybíráme a zahazujeme včetně hran, které vedou do/z nich.
    A případně přidáváme do~fronty vrcholy, kterým při tom klesl jeden ze stupňů na 0.
    Vymažou se tím slepé uličky, které by vadily v podkroku~9.
  \endlist
  Takto kroky 5 a 12 dohromady spotřebují čas $\O(m)$.
  \:Jeden průchod vnějším cyklem tedy trvá $\O(mn)$.
  \:Jak za chvíli dokážeme, každým průchodem vnějším cyklem $l$ vzroste, takže průchodů
    bude maximálně~$n$ a celý algoritmus tak poběží v~čase $\O(n^2m)$.
\endlist

\s{Korektnost algoritmu:}
Když se Dinicův algoritmus zastaví, nemůže už existovat žádná zlepšující cesta
(viz krok~4) a tehdy, jak už víme z~analýzy F-F algoritmu, je nalezený tok maximální.

\s{Věta:}
V~každém průchodu Dinicova algoritmu vzroste $l$ alespoň~o~1.

\proof
Podíváme se na~průběh jednoho průchodu vnějším cyklem.
Délku aktuálně nejkratší $st$-cesty označme~$l$.
Všechny původní cesty délky~$l$ se během průchodu zaručeně nasytí, protože
tok~$f_B$ je blokující. Musíme však dokázat, že nemohou vzniknout žádné
nové cesty délky~$l$ nebo menší. V~síti rezerv totiž mohou hrany nejen
ubývat, ale i přibývat: pokud pošleme tok po~hraně, po~které ještě nic
neteklo, tak v~protisměru z~dosud nulové rezervy vyrobíme nenulovou.
Rozmysleme si tedy, jaké hrany mohou přibývat:

Vnější cyklus začíná s nepročištěnou sítí. Příklad takové sítě je na~následujícím obrázku.
Po~pročištění zůstanou v~síti jen černé hrany, tedy hrany vedoucí z~$i$-té
vrstvy do~$(i+1)$-ní. Červené a modré\foot{Modré jsou ty, které vedou v rámci jedné vrstvy,
červené vedou zpět či za~spotřebič či do~slepých uliček. Při vytištění na papír vypadají všechny černě.}
se zahodí.

Nové hrany mohou vznikat výhradně jako opačné k~černým hranám (hrany ostatních barev
padly za oběť pročištění). Jsou to tedy vždy zpětné hrany vedoucí z~$i$-té vrstvy do~$(i-1)$-ní.
Vznikem nových hran by proto mohly vzniknout nové $st$-cesty, které používají
zpětné hrany. Jenže $st$-cesta, která použije zpětnou hranu, musí alespoň jednou skočit
o~vrstvu zpět a nikdy nemůže skočit o~více než jednu vrstvu dopředu, a~proto je její
délka alespoň $l+2$. Tím je věta dokázána. \qed

% posunut dále, aby vyšla sazba
\figure{dinic-neprocistenasit.eps}{Nepročištěná síť. Obsahuje zpětné hrany, hrany uvnitř vrstvy a slepé uličky.}{0.45\hsize}

% HACK
\vskip -10pt

\figure{dinic-cestashranouzpet.eps}{Cesta užívající novou zpětnou hranu}{0.4\hsize}

\h{Poznámky}

\itemize\ibull
\:Není potřeba tak puntičkářské čištění. Vrcholy se vstupním stupněm 0 nám
   nevadí -- stejně se do nich nedostaneme. Vadí jen vrcholy s výstupním stupněm 0, kde by mohl
   havarovat postup v podkroku 9.
\:Je možné dělat prohledávání a čištění současně. Jednoduše prohledáváním do~hloubky:
   \uv{Hrrr na ně!} a když
   to nevyjde (dostaneme se do slepé uličky), kus ustoupíme a při ústupu čistíme síť
   odstraňováním slepé uličky.
\:Už při prohledávání si rovnou udržujeme minimum z rezerv a při zpáteční cestě
   opravujeme kapacity. Snadno zkombinujeme s~prohledáváním do~hloubky.
\:V průběhu výpočtu udržujeme jen síť rezerv a tok vypočteme až nakonec z rezerv a kapacit.
\:Když budeme chtít hledat minimální řez, spustíme po~Dinicovu algoritmu ještě jednu iterací F-F
   algoritmu.
\endlist

\h{Speciální sítě (ubíráme na obecnosti)}

Při převodu různých úloh na~hledání maximálního toku často dostaneme síť v~nějakém
speciálním tvaru -- třeba s~omezenými kapacitami či stupni vrcholů. Podíváme se
proto podrobněji na~chování Dinicova algoritmu v~takových případech a ukážeme,
že často pracuje překvapivě efektivně.

\s{Jednotkové kapacity:}
Pokud síť neobsahuje cykly délky~2 (dvojice navzájem opačných hran), všechny rezervy
jsou jen 0 nebo~1. Pokud obsahuje, mohou rezervy být i dvojky, a~proto síť upravíme tak,
že ke~každé hraně přidáme hranu opačnou s~nulovou kapacitou a rezervu proti směru
toku přiřkneme jí. Vzniknou tím sice paralelní hrany, ale to tokovým algoritmům
nikterak nevadí.%
\foot{Často se to implementuje tak, že protisměrné hrany vůbec nevytvoříme a když
hranu nasytíme, tak v~síti rezerv prostě obrátíme její orientaci.}

Při hledání blokujícího toku tedy budou mít všechny hrany na~nalezené $st$-cestě
stejnou, totiž jednotkovou, rezervu, takže vždy z~grafu odstraníme celou cestu.
Když máme $m$ hran, počet zlepšení po cestách délky $l$ bude maximálně $m/l$.
Proto složitost podkroků 9, 10 a 11 bude $m/l \cdot \O(l) = \O(m)$.%
\foot{Nebo by šlo argumentovat, tím že každou hranu použijeme jen $1\times$.}
Tedy pro jednotkové kapacity dostáváme složitost $\O(nm)$.

\s{Jednotkové kapacity znovu a lépe:}
Vnitřní cyklus lépe udělat nepůjde. Je potřeba alespoň lineární čas pro čištění.
Můžeme se ale pokusit lépe odhadnout počet iterací vnějšího cyklu.

Sledujme stav sítě po $k$ iteracích vnějšího cyklu a pokusme se odhadnout, kolik iterací
ještě algoritmus udělá. Označme~$l$ délku nejkratší $st$-cesty.
Víme, že $l>k$, protože v každé iteraci vzroste $l$ alespoň o 1.

Máme tok $f_k$ a chceme dostat maximální tok $f$. Rozdíl $f-f_k$ je tok v~síti rezerv
(tok v~původní síti to ovšem být nemusí!), označme si ho~$f_R$.
Každá iterace velkého cyklu zlepší $f_k$ alespoň o 1. Tedy nám zbývá ještě
nejvýše $\vert f_R \vert$ iterací.
Proto bychom chtěli omezit velikost toku $f_R$. Například řezem.

Najdeme v síti rezerv nějaký dost malý řez $C$. Kde ho vzít?\foot{Přeci v řeznictví. Kdepak, spíše v cukrárně.
Myslíte, že v cukrárně mají Dinicovy řezy? Myslím, že v cukrárně je většina řezů minimální. {\sl (odposlechnuto na~přednášce)}}
Počítejme jen hrany zleva doprava. Těch je jistě nejvýše $m$ a tvoří alespoň $k$ rozhraní mezi
vrstvami. Tedy existuje rozhraní vrstev
s~nejvýše $m/k$ hranami\foot{Princip holubníku a nějaká ta $\pm1$.}.
Toto rozhraní je řez. Tedy existuje řez~$C$, pro nějž $\vert C\vert \leq m/k$,
a~algoritmu zbývá maximálně $m/k$ dalších kroků.
Celkový počet kroků je nejvýš $k + m/k$, takže stačí zvolit $k = \sqrt{m}$ a získáme
odhad na~počet kroků $\O(\sqrt{m})$.

Tím jsme dokázali, že celková složitost Dinicova algoritmu pro jednotkové
kapacity je $\O(m^{3/2})$. Tím jsme si pomohli pro řídké grafy.

\vbox{
\inlinefig{dinic-vrcholrez.eps}{0.2\hsize}
\s{Jednotkové kapacity a jeden ze stupňů roven 1:}
Úlohu hledání maximálního párování v~bipartitním grafu, případně hledání
vrcholově disjunktních cest v~obecném grafu lze převést (viz předchozí kapitola)
na~hledání maximálního toku v~síti, v~níž má každý vrchol~$v\ne s,t$ buďto vstupní
nebo výstupní stupeň roven jedné.
Pro takovou síť můžeme předchozí odhad ještě trošku upravit. Pokusíme
se nalézt v síti po~$k$~krocích nějaký malý řez. Místo rozhraní budeme hledat jednu malou
vrstvu a z~malé vrstvy vytvoříme malý řez tak, že pro každý vrchol z~vrstvy vezmeme tu hranu,
která je ve~svém směru sama.

}

Po $k$ krocích máme alespoň $k$ vrstev, a~proto existuje vrstva $\delta$ s nejvýše $n/k$ vrcholy.
Tedy existuje řez $C$ o~velikosti $\vert C\vert \leq n/k$ (získáme z vrstvy $\delta$ výše popsaným postupem).
Algoritmu zbývá do konce $\leq n/k$ iterací vnějšího cyklu, celkem tedy udělá $k + n/k$ iterací.
Nyní stačí zvolit $k = \sqrt{n}$ a složitost
celého algoritmu vyjde $\O(\sqrt{n}\cdot m)$.

Mimochodem, hledání maximálního párování pomocí Dinicova algoritmu je také ekvivalentní
známému Hopcroft-Karpově algoritmu \cite{hopcroft:matching}. Ten je založen na~střídavých
cestách z~předchozí kapitoly a v~každé iteraci nalezne množinu vrcholově disjuktních
nejkratších střidavých cest, která je maximální vzhledem k~inkluzi.
Touto množinou pak aktuální párování přexoruje, čímž ho zvětší. Všimněte si, že tyto
množiny cest odpovídají právě blokujícím tokům v~pročištěné síti rezerv, takže můžeme
i~zde použít náš odhad na~počet iterací.

\s{Třetí pokus pro jednotkové kapacity bez omezení na stupně vrcholů v síti:}
Hlavní myšlenkou je opět po $k$ krocích najít nějaký malý řez. Najdeme dvě malé
sousední vrstvy a všechny hrany mezi nimi budou tvořit námi hledaný malý řez.
Budeme tentokrát předpokládat, že naše síť není multigraf, případně že
násobnost hran je alespoň omezena konstantou.

Označme $s_i$ počet vrcholů v $i$-té vrstvě. Součet počtu vrcholů ve dvou
sousedních vrstvách označíme $t_i = s_i + s_{i+1}$. Bude tedy platit nerovnost:
$$\sum_i t_i \leq 2\sum_i s_i \leq 2n.$$
Podle holubníkového principu existuje $i$ takové, že $t_i \leq 2n/k$, čili
$s_i + s_{i+1} \leq 2n/k$. Počet hran mezi $s_i$ a $s_{i+1}$ je velikost řezu
$C$, a to je shora omezeno $s_i \cdot s_{i+1}$. Nejhorší případ nastane, když $s_i = s_{i+1} = n/k$,
a~proto $\vert C\vert \leq {(n/k)}^2$.
Proto počet iterací velkého cyklu je $\leq k + {(n/k)}^2$.
Chytře zvolíme $k = n^{2/3}$. Složitost celého algoritmu pak bude $\O(n^{2/3}m)$.

\s{Obecný odhad pro celočíselné kapacity:}
Tento odhad je založen na velikosti
maximálního toku $f$ a předpokladu celočíselných kapacit.
Za jednu iteraci velkého cyklu projdeme malým cyklem maximálně tolikrát,
o kolik se v něm zvedl tok, protože každá zlepšující cesta ho zvedne alespoň o $1$.
Zlepšující cesta se tedy hledá maximálně  $\vert f\vert$-krát za celou dobu běhu algoritmu.
Cestu najdeme v čase $\O(n)$. Celkem na~hledání
cest spotřebujeme $\O(\vert f\vert\cdot n)$ za celou dobu běhu algoritmu.

Nesmíme ale zapomenout na čištění. V jedné iteraci velkého cyklu nás stojí čištění $\O(m)$ a velkých
iterací je $\leq n$. Proto celková složitost algoritmu činí $\O(\vert f\vert n + nm)$

Pokud navíc budeme předpokládat, že kapacita hran je nejvýše~$C$ a $G$ není multigraf,
můžeme využít toho, že $\vert f\vert \le Cn$ (omezeno řezem okolo~$s$) a získat odhad
$\O(Cn^2 + nm)$.

\h{Škálování kapacit}

Pokud jsou kapacity hran větší celá čísla omezená nějakou konstantou~$C$, můžeme si pomoci následujícím algoritmem.
Jeho základní myšlenka je podobná, jako u~třídění čísel postupně po řádech pomocí
radix-sortu neboli přihrádkového třídění. Pro jistotu si ho připomeňme. Algoritmus nejprve setřídí čísla podle poslední
(nejméně významné) cifry, poté podle předposlední, předpředposlední a tak dále.

%\figure{dinic-sort.eps}{Kroky postupného třídění podle řádů}{0.4\hsize}

V našem případě budeme postupně budovat sítě čím dál podobnější zadané
síti a v~nich počítat toky, až nakonec získáme tok pro ni.

Přesněji: Maximální tok v síti $G$ budeme hledat tak, že hranám postupně
budeme zvětšovat kapacity bit po bitu v~binárním zápisu až k~jejich skutečné kapacitě.
Přitom po~každém posunu zavoláme Dinicův algoritmus, aby dopočítal maximální tok.
Pomocí předchozího odhadu ukážeme, že jeden takový krok nebude příliš drahý.

\figure{dinic-scaling-original.eps}{Původní síť, na hranách jsou jejich kapacity v binárním zápisu}{0.3\hsize}

Označme $k$ index nejvyššího bitu v~zápisu kapacit v~zadané síti ($k = \lfloor \log_2C \rfloor$).
Postupně budeme budovat sítě $G_i$ s~kapacitami $c_i(e) = \lfloor {c(e) / 2^{k-i}} \rfloor$.
$G_0$ je nejořezanější síť, kde každá hrana má kapacitu rovnou nejvyššímu bitu v~binárním zápisu
její skutečné kapacity, až $G_k$ je původní síť $G$.

\figure{dinic-scaling-g.eps}{Sítě $G_0$, $G_1$ a $G_2$, jak vyjdou pro síť z~předchozího obrázku}{0.9\hsize}

\>Přitom pro kapacity v~jednotlivých sítích platí:

$$ c_{i+1}(e) = \left\{
\eqalign{
           2c_i(e),   &\hbox{\quad pokud $(k-i-1)$-tý bit je 0,}  \cr
           2c_i(e)+1, &\hbox{\quad pokud $(k-i-1)$-tý bit je 1.}  \cr}
\right.
$$

Na spočtení maximálního toku $f_i$ v síti $G_i$ zavoláme Dinicův algoritmus,
ovšem do začátku nepoužijeme nulový tok, nýbrž tok $2f_{i-1}$. Rozdíl toku z inicializace
a výsledného bude malý, totiž:

\s{Lemma:} $\vert f_i\vert - \vert 2f_{i-1}\vert \leq m.$

\proof
Vezmeme minimální řez $R$ v~$G_{i-1}$. Podle F-F věty víme, že $\vert f_{i-1}\vert = \vert R\vert$.
Řez $R$ obsahuje $\leq m$ hran, a~tedy v~$G_{i}$ má tentýž řez kapacitu maximálně $2\vert R\vert+m$.
Maximální tok je omezen každým řezem, tedy i řezem $R$, a~proto tok vzroste nejvýše o~$m$.
\qed

Podle předchozího odhadu pro celočíselné kapacity výpočet toku $f_i$ trvá $\O(mn)$.
Takový tok se bude počítat $k$-krát, pročež celková složitost vyjde $\O(mn\log C)$.

\h{Algoritmus tří Indů}

Překvapení na~konec: Dinicův algoritmus lze poměrně snadno zrychlit i ve~zcela obecném
případě. Malhotra, Kumar a Maheshwari vymysleli efektivnější algoritmus \cite{threeinds}
na~hledání blokujícího toku ve~vrstevnaté síti, který běží v~čase $\O(n^2)$ a použijeme-li
ho v~Dinicově algoritmu, zrychlíme hledání maximálního toku na~$\O(n^3)$.
Tento algoritmus vešel do~dějin pod názvem Metoda tří Indů.

Mějme tedy nějakou vrstevnatou síť. Začneme s~nulovým tokem a budeme ho postupně zlepšovat.
Průběžně si budeme udržovat rezervy hran~$r(e)$\foot{počítáme pouze rezervu ve~směru hrany, neboť
nám stačí najít blokující tok, ne~nutně maximální} a také následující rezervy vrcholů:

\s{Definice:} $r^+(v)$ je součet rezerv všech hran vstupujících do~$v$, $r^-(v)$ součet
rezerv hran vystupujících z~$v$ a konečně $r(v):=\min(r^+(v),r^-(v))$.

V~každé iteraci algoritmu nalezneme vrchol s~nejnižším~$r(v)$ a zvětšíme tok tak, aby se
tato rezerva vynulovala. Za~tímto účelem nejdříve přepravíme $r(v)$ jednotek toku ze~zdroje
do~$v$: u~každého vrcholu~$w$ si budeme pamatovat {\I plán} $p(w)$, což bude množství
tekutiny, které potřebujeme dostat ze~zdroje do~$w$. Nejdříve budou plány všude nulové
až na~$p(v)=r(v)$. Pak budeme postupovat po~vrstvách směrem ke~zdroji a plány všech
vrcholů splníme tak, že je převedeme na~plány vrcholů v~následující vrstvě, až doputujeme
ke~zdroji, jehož plán je splněn triviálně. Nakonec analogickým způsobem protlačíme $r(v)$
jednotek z~$v$ do~spotřebiče.

Během výpočtu průběžně přepočítáváme všechna $r^+$, $r^-$ a~$r$ podle toho, jak se mění
rezervy jednotlivých hran (při každé úpravě rezervy to zvládneme v~konstantním čase)
a síť čistíme stejně jako u~Dinicova algoritmu.

\finalfix{\goodbreak}

\s{Algoritmus:} (hledání blokujícího toku ve~vrstevnaté síti podle tří Indů)

\algo
\:$f_B\leftarrow\<prázdný tok>$.
\:Spočítáme rezervy všech hran a $r^+$, $r^-$ a $r$ všech vrcholů. (Tyto hodnoty
  budeme posléze udržovat při každé změně toku po~hraně.)
\:Dokud v~síti existují vrcholy s~nenulovou rezervou, vezmeme vrchol $v$ s~nejmenším $r(v)$
  a provedeme pro něj: {\I (vnější cyklus)}
\::Převedeme $r(v)$ jednotek toku z~$s$ do~$v$ následovně:
\:::Položíme $p(v)\leftarrow r(v)$, $p(\cdot)=0$.
\:::Procházíme vrcholy sítě po~vrstvách od~$v$ směrem k~$s$. Pro každý vrchol~$w$ provedeme:
\::::Dokud $p(w)>0$:
\:::::Vezmeme libovolnou hranu $uw$ a tok po~ní zvýšíme o~$\delta=\min(r(uw), p(w))$. Tím se
      $p(w)$ sníží~o~$\delta$ a $p(u)$ zvýší~o~$\delta$.
\:::::Pokud se hrana~$uw$ nasytila, odstraníme jí ze sítě a síť dočistíme.
\::Analogicky převedeme $r(v)$ jednotek z~$v$ do~$t$.
\endalgo

\s{Analýza:} Nejprve si všimneme, že cyklus v~kroku~8 opravdu dokáže vynulovat $p(w)$.
Součet všech $p(w)$ přes každou vrstvu je totiž nejvýše roven $r(v)$, takže speciálně každé
$p(w)\le r(v)$. Jenže $r(v)$ jsme vybrali jako nejmenší, takže $p(w)\le r(v)\le r(w)\le r^+(w)$,
a~proto je plánovaný tok kudy přivést. Proto se algoritmus zastaví a vydá blokující tok.

Zbývá odhadnout časovou složitost: Když oddělíme převádění plánů po~hranách (kroky 7--9),
zbytek jedné iterace vnějšího cyklu trvá~$\O(n)$ a těchto iterací je nejvýše~$n$. Všechna převedení
plánu si rozdělíme na~ta, kterými se nějaká hrana nasytila, a~ta, která skončila vynulováním $p(w)$.
Těch prvních je $\O(m)$, protože každou takovou hranu vzápětí odstraníme a čištění, jak už víme,
trvá také lineárně dlouho. Druhý případ nastane pro každý vrchol nejvýše jednou za~iteraci.
Dohromady tedy trvají všechna převedení $\O(n^2)$, stejně jako zbytek algoritmu.
\qed

\h{Přehled variant Dinicova algoritmu}

\medskip

\centerline{\vbox{\halign{# \hfil \quad &# \hfil \cr
\it varianta &\it čas \cr\noalign{\smallskip\hrule\smallskip}
standardní                              &$\O(n^2m)$      \cr
jednotkové kapacity                    &$\O(\sqrt{m}\cdot m) = \O(m^{3/2})$   \cr
jednotkové kapacity, 1 stupeň $\leq 1$  &$\O(\sqrt{n}\cdot m)$   \cr
jednotkové kapacity, prostý graf        &$\O(n^{2/3}m)$    \cr
celočíselné kapacity                    &$\O(\vert f\vert\cdot n + nm)$     \cr
celočíselné kapacity $ \leq C$          &$\O(Cn^2 + mn)$   \cr
celočíselné kapacity $ \leq C$ (škálování)&$\O(mn\log C)$    \cr
tři Indové                            &$\O(n^3)$         \cr
}}}

\references

\bye