Abstrakt
Tento článek podává přehled o mnoha stránkách problému minimální kostry. Sledujeme historii tohoto problému od prvního polynomiálního algoritmu navrženého Borůvkou až po moderní algoritmy Chazella, Pettieho a Ramachandranové.
Studujeme, jak se časová složitost algoritmů mění v závislosti na použitém výpočetním modelu a na dostupnosti náhodných bitů. Také zmiňujeme problém dynamického udržování kostry a další příbuzné problémy.