Intro on RAM data structures.

[saga.git] / mst.tex

diff --git a/mst.tex b/mst.tex
index 10d89de746e036c1d04cddb873cd23a880eec8a6..7e5be9097813a4ab59f639eaa4c520afab9527d8 100644 (file)
--- a/mst.tex
+++ b/mst.tex
@@ -576,24 +576,13 @@ From this we get that the total time complexity is $\O(\sum_i m_i)=\O(\sum_i n/2
 \rem
 There are several other possibilities how to find the MST of a planar graph in linear time.
 For example, Matsui \cite{matsui:planar} has described an algorithm based on simultaneously
-working on the graph and its topological dual. We will show one more linear algorithm soon. The advantage
-of our approach is that we do not need to construct the planar embedding explicitly.
+working on the graph and its topological dual. The advantage of our approach is that we do not need
+to construct the planar embedding explicitly. We will show one more linear algorithm
+in section~\ref{minorclosed}.
 
 \rem
-To achieve the linear time complexity, the algorithm needs a very careful implementation.
-Specifically, when we represent the graph using adjacency lists, whose heads are stored
-in an array indexed by vertex identifiers, we must renumber the vertices in each iteration.
-Otherwise, unused elements could end up taking most of the space in the arrays and the scans of these
-arrays would have super-linear cost with respect to the size of the current graph~$G_i$.
-
-\rem
-The algorithm can be also implemented on the pointer machine. Representation of graphs
-by pointer structures easily avoids the aforementioned problems with sparse arrays,
-but we need to handle the bucket sorting somehow. We can create a small data structure
-for every vertex and use a pointer to this structure as a unique identifier of the vertex.
-We will also keep a list of all vertex structures. During the bucket sort, each vertex
-structure will contain a pointer to the corresponding bucket and the vertex list will
-define the order of vertices (which can be arbitrary).
+To achieve the linear time complexity, the algorithm needs a very careful implementation,
+but we defer the technical details to section~\ref{bucketsort}.
 
 \para
 Graph contractions are indeed a~very powerful tool and they can be used in other MST