Hermes: an efficient algorithm for building Galois sub-hierarchies - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2012

Hermes: an efficient algorithm for building Galois sub-hierarchies

Abstract

Given a binary relation R 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 ^{\alpha}}), where n is the number of objects or attributes, m is the size of the relation, and n ^{\alpha} is the time required to perform matrix multiplication (currently \alpha = 2.376).
Fichier principal
Vignette du fichier
paperAnneBerry.pdf (232.12 Ko) Télécharger le fichier
Origin Publisher files allowed on an open archive
Loading...

Dates and versions

lirmm-00743882 , version 1 (21-10-2012)

Identifiers

  • HAL Id : lirmm-00743882 , version 1

Cite

Anne Berry, Marianne Huchard, Amedeo Napoli, Alain Sigayret. Hermes: an efficient algorithm for building Galois sub-hierarchies. CLA: Concept Lattices and their Applications, Oct 2012, Fuengirola, Málaga, Spain. pp.21-32. ⟨lirmm-00743882⟩
950 View
348 Download

Share

More