## 3 Algorithms
### Manipulation Part  
In the traversal described in the previous subsection, whenever we visit a node \(f\) and select the next node \(g\), we update the current partition \(p\) by invoking the function \(\mathrm{Update}\). Namely, when we find an element \(e_{i}\) which is separable from the other elements in the same block, we move \(e_{i}\) to an appropriate block so that each block consists of inseparable elements with respect to the information up to this time. For example, let us see the computing process in Figure 3 step by step. Suppose that we arrive at the label \(3\) node after the first visit of \(\top\). At this time \(p=\{S\setminus\{e_{4}\},\{e_{4}\}\}\). When we go to the label \(5\) node along the HI arc, the element \(e_{3}\) becomes in a HI state while the other elements are in a LO state. Thus we create a new block and move \(e_{3}\) into it. We furthermore memorize the arc from the previous block \(b\), which \(e_{3}\) was in, to the new block \(b^{\prime}\), which now consists of only \(e_{3}\). This is necessary because \(e_{5}\in b\) soon becomes in a HI state and we have to insert \(e_{5}\) into \(b^{\prime}\), not a new block. We then reach \(\top\) and go back to the label \(2\) node on the left side. The element \(e_{2}\in b\) becomes in a HI state, but we never insert \(e_{2}\) into \(b^{\prime}\), since insertion is allowed only within the period from the creation of \(b^{\prime}\) until the arrival at \(\top\). Therefore, we create a new block \(b^{\prime\prime}\) and move \(e_{2}\) into it. We furthermore redirect the outgoing arc of \(b\) to the new block \(b^{\prime\prime}\). In this way, we update the current partition \(p\), the graph structure \(G\) on the blocks of \(p\), and the set \(B_{\mathrm{new}}\) of blocks created since the last visit of \(\top\). The function \(\mathrm{Update}\) is formally described in Algorithm 2. Let \(e_{i}\) and \(e_{j}\) be the elements corresponding to the current node \(f\) and the next node \(g\), respectively. We move \(e_{i}\) to another block only if the arc type of \(e_{i}\) changes from LO to HI or from HI to LO. Note that we need not move \(e_{i}\) in the other cases. This move operation for \(e_{i}\) is done in the former part of the function \(\mathrm{Update}\) by invoking the function \(\mathrm{Move}\). The destination block of \(e_{i}\) is determined by means of the auxiliary data structures \(G\) and \(B_{\mathrm{new}}\). The \(G\) defines a parent-child relation between the blocks of the current partition \(p\). That a block \(b\) is a parent of a block \(b^{\prime}\) implies that \(b^{\prime}\) is formed by elements which most recently went out from \(b\). Moving elements of \(b\) to \(b^{\prime}\) is allowed only within the period from the creation of \(b^{\prime}\) until the arrival at \(\top\), which can be decided by using \(B_{\mathrm{new}}\). There may be some nodes hidden between the current node \(f\) and the next node \(g\) due to the node elimination rule. Let \(e_{l}\) be the element corresponding to such a hidden node. Since \(e_{l}\) is now in a LO state, it suffices to move \(e_{l}\) only if the previous arc type is HI. This computation is done in the latter part of the function \(\mathrm{Update}\). We are now ready to state the time complexity of our algorithm. Recall that a branch node is an internal node whose two children have paths leading to \(\top\). **Theorem 3.2**. : _Let \(k\) be the maximum number of HI arcs in a path from the root to \(\top\). Let \(m\) be the number of branch nodes. Let \(n\) be the size of a ground set. Algorithm 1 correctly computes a co-occurrence partition. It can be implemented to run in time proportional to \(n+km\)._  
Proof. : From Lemma 3.1 and the observations up to here, we can easily verify that Algorithm 1 correctly computes a co-occurrence partition. Throughout this proof, we mean by a period the time period from a visit of \(\top\) to the next visit. The time necessary to create the initial partition is proportional to \(n\).