In this paper, we present an implicit data structure for the representation of a partial lattice ${\cal L}=(\prec, {\cal N})$ which allows to test the partial order relation among two given elements in constant time. The data structure proposed has an overall $O(n\sqrt{n})$ -space complexity, where $n$ is the size of ground set ${\cal N}$, which we will prove to be optimal in the worst case. Hence, we derive an overall $O(n\sqrt{n})$-space*time bound for the relation testing problem so beating the $O(n^2)$ bottle-neck representing the present complexity. The overall pre-processing time is $O(n^2)$.
A Data Structure for Lattices Representation.
VOCCA, PAOLA
1997-01-01
Abstract
In this paper, we present an implicit data structure for the representation of a partial lattice ${\cal L}=(\prec, {\cal N})$ which allows to test the partial order relation among two given elements in constant time. The data structure proposed has an overall $O(n\sqrt{n})$ -space complexity, where $n$ is the size of ground set ${\cal N}$, which we will prove to be optimal in the worst case. Hence, we derive an overall $O(n\sqrt{n})$-space*time bound for the relation testing problem so beating the $O(n^2)$ bottle-neck representing the present complexity. The overall pre-processing time is $O(n^2)$.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
