Modules and PQ-trees in Robinson spaces
share
A Robinson space is a dissimilarity space (X,d) on n points for which there exists a compatible order, i.e. a total order < on X such that x<y<z implies that d(x,y)≤ d(x,z) and d(y,z)≤ d(x,z). Recognizing if a dissimilarity space is Robinson has numerous applications in seriation and classification. A PQ-tree is a classical data structure introduced by Booth and Lueker to compactly represent a set of related permutations on a set X. In particular, the set of all compatible orders of a Robinson space are encoded by a PQ-tree. An mmodule is a subset M of X which is not distinguishable from the outside of M, i.e. the distances from any point of X∖ M to all points of M are the same. Mmodules define the mmodule-tree of a dissimilarity space (X,d). Given p∈ X, a p-copoint is a maximal mmodule not containing p. The p-copoints form a partition of X∖{p}. There exist two algorithms recognizing Robinson spaces in optimal O(n^2) time. One uses PQ-trees and one uses a copoint partition of (X, d). In this paper, we establish correspondences between the PQ-trees and the mmodule-trees of Robinson spaces. More precisely, we show how to construct the mmodule-tree of a Robinson dissimilarity from its PQ-tree and how to construct the PQ-tree from the odule-tree. To establish this translation, additionally to the previous notions, we introduce the notions of δ-graph G_δ of a Robinson space and of δ-mmodules, the connected components of G_δ. We also use the dendrogram of the subdominant ultrametric of d. All these results also lead to optimal O(n^2) time algorithms for constructing the PQ-tree and the mmodule tree of Robinson spaces.
READ FULL TEXT