Hermes: a simple and efficient algorithm for building the AOC-poset of a binary relation - Archive ouverte HAL Access content directly
Journal Articles Annals of Mathematics and Artificial Intelligence Year : 2014

## Hermes: a simple and efficient algorithm for building the AOC-poset of a binary relation

(1) , (2) , (3) , (4) , (1)
1
2
3
4
Anne Berry
• Function : Author
• PersonId : 858556
Alain Gutierrez
Marianne Huchard
Amedeo Napoli

#### Abstract

Given a relation $\Rel\subseteq\Obj\times\Attr$ on a set $\Obj$ of objects and a set $\Attr$ of attributes, the AOC-poset (Attribute/Object Concept poset), is the partial order defined on the introducers'' of objects and attributes in the corresponding concept lattice. In this paper, we present \hermes, a simple and efficient algorithm for building an AOC-poset which runs in $O(min\{nm,\,n^\alpha\})$, where $n$ is the number of objects and attributes, $m$ is the size of the relation, and $n^\alpha$ is the time required to perform matrix multiplication (currently $\alpha=2.376$). Finally, we compare the execution time of \hermes~with the execution time of other published algorithms which compute the AOC-poset: \ares, \ceres~and \pluton. We characterize the cases where each of these algorithms is relevant to use.

### Dates and versions

hal-01101144 , version 1 (09-01-2015)

### Identifiers

• HAL Id : hal-01101144 , version 1
• DOI :

### Cite

Anne Berry, Alain Gutierrez, Marianne Huchard, Amedeo Napoli, Alain Sigayret. Hermes: a simple and efficient algorithm for building the AOC-poset of a binary relation. Annals of Mathematics and Artificial Intelligence, 2014, 72 (1), pp.45-71. ⟨10.1007/s10472-014-9418-6⟩. ⟨hal-01101144⟩

### Export

BibTeX TEI Dublin Core DC Terms EndNote Datacite

433 View