An Efficient Data Structure for Lattice Operations

In this paper, we consider the representation and management of an element set on which a lattice partial order relation is defined. In particular, let $n$ be the element set size, we present an \nradn-space {\em implicit} data structure for performing the following set of basic operations: \begin {itemize} \item[1.] test the presence of an order relation between two given elements, in constant time; \item[2.] find a path between two elements whenever one exists, in $O(l)$ steps, where $l$ is the path length; \item[3.] compute the successors and/or predecessors set of a given element, in $O(h)$ steps, where $h$ is the size of the returned set; \item[4.] given two elements, find all elements between them, in time $O(k\log d)$, where $k$ is the size of the returned set and $d$ is the maximum indegree or outdegree in the transitive reduction of the order relation; \item[5.] given two elements, find the least common ancestor and/or the greatest common successor in $O(\sqrt{n})$-time; \item[6.] given $k$ elements, find the least common ancestor and/or the greatest common successor in $O(\sqrt{n}+k \log n)$\footnote{Unless stated otherwise, all logarithms are to the base 2.}-time. \end {itemize} The pre-processing time is $O(n^2)$. Focusing on the first operation, representing the building-box for all the others, we derive an overall \nradn-space$\times$time bound which beats the order $n^2$ bottle-neck representing the present complexity for this problem. Moreover, we will show that the complexity bounds for the first three operations are optimal with respect to the worst case. Additionally, a stronger result can be derived. In particular, it is possible to represent a lattice in space $O(n\sqrt{t})$, where $t$ is the minimum number of disjoint chains which partition the element set.