-Chazelle popisuje algoritmus se slo¾itostí $\O(m\alpha(m,n))$. Podle Pettieho je mo¾né dosáhnout
-a¾ optima, tedy slo¾itosti $\O(T(m,n))$, kde $T$ je hloubka optimálního rozhodovacího stromu
-pro grafy na~$n$ vrcholech s $m$ hranami (není ale známo, jak ho sestrojit, ani jak je hluboký);
-zajímavé je, ¾e tento algoritmus funguje i na Pointer Machine, tak¾e pokud existuje lineární
-algoritmus na~MST, nepotøebuje sílu RAMu.\foot{O výpoèetních modelech viz pøí¹tí pøedná¹ka.}
+\itemize\ibull
+\:$\O(m\alpha(m,n))$, kde $\alpha(m,n)$ je obdoba inverzní
+ Ackermannovy funkce definovaná podobnì, jako je $\beta(m,n)$ obdobou $\log^*$.
+ \cite{chazelle:ackermann}, \cite{pettie:ackermann}
+\:$\O({\cal T}(m,n))$, kde ${\cal T}(m,n)$ je hloubka optimálního rozhodovacího stromu
+ pro nalezení minimální kostry v~grafech s~patøièným poètem hran a vrcholù
+ \cite{pettie:optimal}.
+ Jeliko¾ ka¾dý deterministický algoritmus zalo¾ený na~porovnávání vah lze popsat rozhodovacím stromem,
+ je tento algoritmus zaruèenì optimální. Jen bohu¾el nevíme, jak optimální stromy vypadají, tak¾e
+ je stále otevøeno, zda lze MST nalézt v~lineárním èase. Nicménì tento algoritmus
+ pracuje i na~Pointer Machine, proèe¾ víme, ¾e pokud je lineární slo¾itosti mo¾né dosáhnout, není k~tomu
+ potøeba výpoèetní síla RAMu.\foot{O výpoèetních modelech viz pøí¹tí kapitola.}
+\:$\O(m)$ pro grafy s~celoèíselnými vahami (na~RAMu) \cite{fw90trans} -- uká¾eme v~jedné
+ z~následujících kapitol.
+\:$\O(m)$, pokud u¾ máme hrany setøídìné podle vah: jeliko¾ víme, ¾e zále¾í jen na~uspoøádání,
+ mù¾eme váhy pøeèíslovat na~$1\ldots m$ a pou¾ít pøedchozí algoritmus.
+\:$\O(m)$ prùmìrnì: randomizovaný algoritmus, který pro libovolný vstupní graf dobìhne v~oèekávaném
+ lineárním èase~\cite{karger:randomized}.
+\:Na~zji¹tìní, zda je zadaná kostra minimální, staèí $\O(m)$ porovnání \cite{komlos:verify} a dokonce
+ lze v~lineárním èase zjistit, která to jsou \cite{king:verify}. Z~toho ostatnì vychází pøedchozí
+ randomizovaný algoritmus.
+\endlist