In this paper, we present an implicit data structure for the representation of a partial lattice L = (<, 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 root n)-space complexity, where n is the size of ground set, N, which we will prove to be optimal in the worst case. Hence, we derive an overall O(n root n)-space*time bound for the relation testing problem thus beating the O(n(2)) bottle-neck representing the present complexity. The overall pre-processing time is O(n(2)).
Talamo, M., Vocca, P. (1997). A data structure for lattice representation. In Theoretical Computer Science (pp.373-392). AMSTERDAM : ELSEVIER SCIENCE BV.
A data structure for lattice representation
TALAMO, MAURIZIO;
1997-01-01
Abstract
In this paper, we present an implicit data structure for the representation of a partial lattice L = (<, 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 root n)-space complexity, where n is the size of ground set, N, which we will prove to be optimal in the worst case. Hence, we derive an overall O(n root n)-space*time bound for the relation testing problem thus beating the O(n(2)) bottle-neck representing the present complexity. The overall pre-processing time is O(n(2)).I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
