An Efficient Data Structure for Lattice Operations
Maurizio Talamo, Paola Vocca · SIAM Journal on Computing · 1999
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 radn-space implicit data structure for performing the following set of basic operations: 1. Test the presence of an order relation between two given elements, in constant time. 2. Find a path between two elements whenever one exists, in O(l) steps, where l is the path length. 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. 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 in-degree or out-degree in the transitive reduction of the order relation. 5. Given two elements, find the least common ancestor and/or the greatest common successor in $O(\sqrt{n})$-time. 6. Given k elements, find the least common ancestor and/or the greatest common successor in $O(\sqrt{n}+k \log n)$time. (Unless stated otherwise, all logarithms are to the base 2.) The preprocessing time is O(n 2 ). Focusing on the first operation, representing the building-box for all the others, we derive an overall radn-space\,$\times$\,time bound which beats the order n 2 bottleneck 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.