Hermes: an efficient algorithm for building Galois sub-hierarchies
Anne Berry, Marianne Huchard, Amedeo Napoli, Alain Sigayret · 2012
Abstract. Given a relation R ⊆ O × A on a set O of objects and a set A of attributes, the Galois sub-hierarchy (also called AOC-poset) is the partial order on the introducers of objects and attributes in the corresponding concept lattice. We present a new efficient algorithm for building a Galois sub-hierarchy which runs in O(min{nm, n α}), where n is the number of objects or attributes, m is the size of the relation, and n α is the time required to perform matrix multiplication (currently α = 2.376).