A fast algorithm for building lattices
This paper presents a simple, efficient algorithm to compute the covering graph of the lattice generated by a family B of subsets of a set X. The implementation of this algorithm has O((\X\ + \B\).\B\) time complexity per lattice element. This improves previous algorithms of Bordat (1986), Ganter and Kuznetsov (1998) and Jard et al. (1994). This algorithm can be used to compute the Galois (concept) lattice, the maximal antichains lattice or the Dedekind-MacNeille completion of a partial order, without increasing time complexity. (C) 1999 Elsevier Science B.V. All rights reserved.
algorithms lattice family of sets data structure