Indové Malhotra, Kumar a Maheshawari v roce 1978 vymysleli efektivnější algoritmus, jak nalézt blokující tok v čisté síti. Jejich metoda běží v čase $\OO(n^2)$, což zlepšuje čas Dinicova algoritmu na $\OO(n^3)$.

Pro každý vrchol si spočítáme, jak velký tok může protékat skrz vrchol. Někdy místo “průtok skrz vrchol” říkáme, jak velký tok jde protlačit skrz vrchol. Největší možný průtok přes vrchol $v$ nazveme rezervou vrcholu $v$ a označíme ho $R(v):=\min\{R^+(v), R^-(v) \,\}$, kde

$$R^+(v)=\sum_{xv\in E } r(xv),$$
$$R^-(v)=\sum_{vx\in E } r(vx).$$
nalezení blokujícího toku v čisté síti (podle tří Indů):

	 spočítej $R(v)$ pro každý $v\in V$
	 while $V\not=\emptyset$ do
	 	 $v_0 := $ vrchol $v\in V$ s minimálním $R(v)$
	 	 if $R(v_0)=0$ then
	 	 	 $V:=V\setminus \{v_0\}$
	 	 	 uprav $R(v)$ pro sousedy $v_0$
	 	 else
	 	 	 najdi tok velikosti $R(v_0)$ procházející vrcholem $v_0$ 
	 	 	 pomocí protlačení doleva a doprava a uprav hodnoty $R(v)$

Kroky $7$–$9$ odpovídají pročišťování čisté sítě. Z grafu vyloučíme vrchol $v_0$ i s hranami, které vedou z $v_0$ nebo do $v_0$. Kromě odstranění vrcholů zpracovaných v předchozím průběhu cyklu se takto odstraňují i slepé uličky (rozmyslete si, jak mohou slepé uličky vzniknout a jak je algoritmus odstraní).

Krok $4$ bude trvat $\OO(m)$. Cyklus proběhne $n$-krát, protože v každé iteraci vyhodíme z množiny vrcholů jeden vrchol. Ostatní kroky, kromě kroku $11$ jsou proveditelné v čase $\OO(n)$. Časovou složitost kroku $11$ budeme počítat zvlášť a budeme ji účtovat hranám a vrcholům sítě.

Jak probíhá krok $11$? Ukážeme si jen protlačování toku doprava. Protlačení toku doleva proběhne symetricky. Protlačování provádíme po vrstvách směrem od $v_0$.

Na začátku dáme do fronty jen $v_0$. Vrcholy z fronty postupně zpracováváme následujícím způsobem. Představme si, že už jsme ve vrcholu $v$, do kterého jsme dotlačili přebytek toku o velikosti $K$. Postupně probíráme hrany, které vedou z vrcholu $v$ doprava, a snažíme se po nich poslat co největší tok. Pokud bude přebytek toku ve $v$ větší, než rezerva probírané hrany, tak hranu nasytíme a postoupíme k další hraně. Z vrcholu vždy vede další hrana, po které můžeme tok poslat, protože $K \leq R(v_0)\leq R^-(v)$. Druhé konce hran, po kterých jsme poslali nějaký tok, vložíme do fronty. Práci s hranami, které jsme nasytili, naúčtujeme hranám (nasycené hrany zmizí z čisté sítě). Práci s poslední hranou, po které jsme poslali nějaký tok, ale nemuseli jsme ji nasytit, naúčtujeme vrcholu $v$. Celkem jsme během algoritmu naúčtovali každé hraně nejvýše jednu jednotku práce a každému vrcholu nejvýše $n$ jednotek práce. Proto je celková časová složitost kroku $11$ rovna $\OO(n^2+m)$.

Časová složitost celého algoritmu na nalezení blokujícího toku podle metody tří Indů je $\OO(n^2)$. To dává časovou složitost nalezení maximálního toku $\OO(n^3)$.


Poznámky k implementaci

Můžeme se vyhnout použití fronty při protlačování toku. Během kroku $2$ si v čase $\OO(m)$ spočítáme topologické uspořádání vrcholů čisté sítě (topologické uspořádání hledáme pro čistou síť pouze jednou). Během protlačování toku doprava postupně v topologickém pořadí probíráme vrcholy, které jsou topologicky větší než $v_0$ a pokud mají kladný přebytek toku, tak přebytek protlačíme do sousedních vrcholů. Podobně při protlačování toku doleva.