A fast incremental algorithm for building lattices
Lhouari Nourine, Olivier Raynaud · Journal of Experimental & Theoretical Artificial Intelligence · 2002
This paper presents an incremental algorithm to compute the covering graph of the lattice generated by a family B of subsets of a totally ordered set X. The implementation of this algorithm has O (((|X| + |B|).|B|).|F|) time complexity, where F is the number of elements in the lattice. This improves the complexity of the previous algorithms which is roughly in O(Min(|X|, |B|)3.|F|). This algorithm may be used in many applications in computer sciences such as the computations of Galois (concept) lattice, the maximal antichains lattice or the Dedekind-MacNeille completion of a partial order. All these lattices can be computed incrementally using this algorithm without increasing time complexity.