From 77268df187a9df3c4e1e2fe1950adb288c67bbe1 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sat, 19 Apr 2008 17:24:01 +0200 Subject: [PATCH] Bits of introduction. --- mst.tex | 19 ++++++++++--------- 1 file changed, 10 insertions(+), 9 deletions(-) diff --git a/mst.tex b/mst.tex index 2cfe5d0..06a1af8 100644 --- a/mst.tex +++ b/mst.tex @@ -41,15 +41,16 @@ spanning tree problem was one of the central topics of the flourishing new disciplines, the previous work was not well known and the algorithms had to be rediscovered several times. -Recently, several significantly faster algorithms were discovered, most notably the -$\O(m\timesbeta(m,n))$-time algorithm by Fredman and Tarjan \cite{ft:fibonacci} and -algorithms with inverse-Ackermann type complexity by Chazelle \cite{chazelle:ackermann} -and Pettie \cite{pettie:ackermann}. - -\FIXME{Write the rest of the history.} - -This chapter attempts to survey the important algorithms for finding the MST and it -also presents several new ones. +In the next 50 years, several significantly faster algorithms were discovered, ranging +from the $\O(m\timesbeta(m,n))$ time algorithm by Fredman and Tarjan \cite{ft:fibonacci}, +over algorithms with inverse-Ackermann type complexity by Chazelle \cite{chazelle:ackermann} +and Pettie \cite{pettie:ackermann}, to another algorithm by Pettie \cite{pettie:optimal} +whose time complexity is provably optimal. + +In the upcoming chapters, we will explore this colorful universe of MST algorithms. +We will meet the standard works of the classics, the clever ideas of their successors, +various approaches to the problem including randomization and solving of important +special cases. %-------------------------------------------------------------------------------- -- 2.39.2