+without indexing of arrays.
+
+We will keep a~list of the per-vertex structures and we will use it to establish the order of~vertices.
+Each such structure will be endowed with a~pointer to the head of the list of items in
+the corresponding bucket. Inserting an~edge to a~bucket can be then done in constant time
+and scanning the contents of all~$n$ buckets takes $\O(n+m)$ time.
+
+At last, we must not forget that while it was easy to \df{normalize} the pairs on the RAM
+by putting the smaller identifier first, this fails on the PM because we can directly
+compare the identifiers only for equality. We can work around this again by bucket-sorting:
+we sort the multiset $\{ (x,i) \mid \hbox{$x$~occurs in the $i$-th pair} \}$ on~$x$.
+Then we reset all pairs and re-insert the values back in their increasing order.
+This also takes $\O(n+m)$.
+
+\paran{Tree isomorphism}%
+Another nice example of pointer-based radix sorting is a~Pointer Machine algorithm for
+deciding whether two rooted trees are isomorphic. Let us assume for a~moment that
+the outdegree of each vertex is at most a~fixed constant~$k$. We begin by sorting the subtrees
+of both trees by their depth. This can be accomplished by running depth-first search to calculate
+the depths and bucket-sorting them with $n$~buckets afterwards.
+
+Then we proceed from depth~0 to the maximum depth and for each depth we identify
+the isomorphism equivalence classes of the particular subtrees. We will assign
+unique \df{codes} (identifiers) to all such classes; at most~$n+1$ of them are needed as there are
+$n+1$~subtrees in the tree (including the empty subtree). As the PM does not
+have numbers as an~elementary type, we create a~``\df{yardstick}'' ---a~list
+of $n+1$~distinct items--- and we use pointers to these ``ticks'' as identifiers.
+When we are done, isomorphism of the whole trees can be decided by comparing the
+codes assigned to their roots.
+
+Suppose that classes of depths $0,\ldots,d-1$ are already computed and we want
+to identify those of depth~$d$. We will denote their count of~$n_d$. We take
+a~root of every such tree and label it with an~ordered $k$-tuple of codes
+of its subtrees; when it has less than $k$ sons, we pad the tuple with empty
+subtrees. Tuples corresponding to isomorphic subtrees are identical up to
+reordering of elements. We therefore sort the codes inside each tuple and then
+sort the tuples, which brings the equivalent tuples together.
+
+The first sort (inside the tuples) would be easy on the RAM, but on the PM we
+have to use the normalization trick mentioned above. The second sort is
+a~straightforward $k$-pass bucket sort.
+
+If we are not careful, a~single sorting pass takes $\O(n_d + n)$ time, because
+while we have only $n_d$~items to sort, we have to scan all $n$~buckets. This can
+be easily avoided if we realize that the order of the buckets does not need to be
+fixed --- in every pass, we can use a~completely different order and it still
+does bring the equivalent tuples together. Thus we can keep a~list of buckets
+that are used in the current pass and look only inside these buckets. This way,
+we reduce the time spent in a~single pass to $\O(n_d)$ and the whole algorithm
+takes just $\O(\sum_d n_d) = \O(n)$.
+
+Our algorithm can be easily modified for trees with unrestricted degrees.
+We replace the fixed $d$-tuples by general sequences of codes. The first
+sort does not need any changes. In the second sort, we proceed from the first
+position to the last one and after each bucket-sorting pass we put aside the sequences
+that have just ended. They are obviously not equivalent to any other sequences.
+The time complexity of the second sort is linear in the sum of the lengths of the sequences, which is
+$n_{d+1}$ for depth~$d$. We can therefore decide isomorphism of the whole trees
+in time $\O(\sum_d (n_d + n_{d+1})) = \O(n)$.
+
+The unification of sequences by bucket sorting will be useful in many
+other situations, so we will state it as a~separate lemma:
+
+\lemman{Sequence unification}\id{suniflemma}%
+Partitioning of a~collection of sequences $S_1,\ldots,S_n$, whose elements are
+arbitrary pointers and symbols from a~finite alphabet, to equality classes can
+be performed on the Pointer Machine in time $\O(n + \sum_i \vert S_i \vert)$.
+
+\rem
+The first linear-time algorithm that partitions all subtrees to isomorphism equivalence
+classes is probably due to Zemlayachenko \cite{zemlay:treeiso}, but it lacks many
+details. Dinitz et al.~\cite{dinitz:treeiso} have recast this algorithm in modern
+terminology and filled the gaps. Our algorithm is easier to formulate,
+because it replaces the need for auxiliary data structures by more elaborate bucket
+sorting.
+
+\paran{Topological graph computations}%
+Many graph algorithms are based on the idea of so called \df{micro/macro decomposition:}
+We decompose a~graph to subgraphs on roughly~$k$ vertices and solve the problem
+separately inside these ``micrographs'' and in the ``macrograph'' obtained by
+contraction of the micrographs. If $k$~is small enough, many of the micrographs
+are isomorphic, so we can compute the result only once for each isomorphism class
+and recycle it for all micrographs of that class. On the other hand, the macrograph
+is roughly $k$~times smaller than the original graph, so we can use a~less efficient
+algorithm and it will still run in linear time with respect to the size of the original
+graph.
+
+This kind of decomposition is traditionally used for trees, especially in the
+algorithms for the Lowest Common Ancestor problem (cf.~Section \ref{verifysect}
+and the survey paper \cite{alstrup:nca}) and for online maintenance of marked ancestors
+(cf.~Alstrup et al.~\cite{alstrup:marked}). Let us take a~glimpse at what happens when
+we decompose a~tree with $k$ set to~$1/4\cdot\log n$. There are at most $2^{2k} = \sqrt n$ non-isomorphic subtrees of size~$k$,
+because each isomorphism class is uniquely determined by the sequence of $2k$~up/down steps
+performed by depth-first search of the tree. Suppose that we are able to decompose the input and identify
+the equivalence classes of microtrees in linear time, then solve the problem in time $\O(\poly(k))$ for
+each microtree and finally in $\O(n'\log n')$ for the macrotree of size $n'=n/k$. When we put these pieces
+together, we get an~algorithm for the whole problem which achieves time complexity $\O(n
++ \sqrt{n}\cdot\poly(\log n) + n/\log n\cdot\log(n/\log n)) = \O(n)$.
+
+Decompositions are usually implemented on the RAM, because subgraphs can be easily
+encoded in numbers, and these can be then used to index arrays containing the precomputed
+results. As the previous algorithm for subtree isomorphism shows, indexing is not strictly
+required for identifying equivalent microtrees and it can be replaced by bucket
+sorting on the Pointer Machine. Buchsbaum et al.~\cite{buchsbaum:verify} have extended
+this technique to general graphs in form of so called topological graph computations.
+Let us define them.
+
+\defn
+A~\df{graph computation} is a~function that takes a~\df{labeled undirected graph} as its input. The labels of
+vertices and edges can be arbitrary symbols drawn from a~finite alphabet. The output
+of the computation is another labeling of the same graph. This time, the vertices and
+edges can be labeled with not only symbols of the alphabet, but also with pointers to the vertices
+and edges of the input graph, and possibly also with pointers to outside objects.
+A~graph computation is called \df{topological} if it produces isomorphic
+outputs for isomorphic inputs. The isomorphism of course has to preserve not only
+the structure of the graph, but also the labels in the obvious way.
+
+\obs
+The topological graph computations cover a~great variety of graph problems, ranging
+from searching for matchings or Eulerian tours to finding Hamilton circuits.
+The MST problem itself however does not belong to this class, because we do not have any means
+of representing the edge weights as labels, unless there is only a~fixed amount
+of possible values.
+
+As in the case of tree decompositions, we would like to identify the equivalent subgraphs
+and process only a~single instance from each equivalence class. The obstacle is that
+graph isomorphism is known to be computationally hard (it is one of the few
+problems that are neither known to lie in~$\rm P$ nor to be $\rm NP$-complete;
+see Arvind and Kurur \cite{arvind:isomorph} for recent results on its complexity).
+We will therefore manage with a~weaker form of equivalence, based on some sort
+of graph encodings:
+
+\defn
+A~\df{canonical encoding} of a~given labeled graph represented by adjacency lists
+is obtained by running the depth-first search on the graph and recording its traces.
+We start with an~empty encoding. When we enter
+a~vertex, we assign an~identifier to it (again using a~yardstick to represent numbers)
+and we append the label of this vertex to the encoding. Then we scan all back edges
+going from this vertex and append the identifiers of their destinations, accompanied
+by the edges' labels. Finally we append a~special terminator to mark the boundary
+between the code of this vertex and its successor.