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;Vocca, P.
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)).
Conference Ordal 94 - Orders, Algorithms and Applications
LYON, FRANCE
JUL, 1994
Rilevanza internazionale
1997
Settore INF/01 - INFORMATICA
English
Computational complexity; Problem solving; Theorem proving; Lattice representation; Data structures
Intervento a convegno
Talamo, M., Vocca, P. (1997). A data structure for lattice representation. In Theoretical Computer Science (pp.373-392). AMSTERDAM : ELSEVIER SCIENCE BV.
Talamo, M; Vocca, P
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2108/41903
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 12
  • ???jsp.display-item.citation.isi??? 8
social impact