Directed binary hierarchies and directed ultrametrics

Israël-César Lerman 1, * Pascale Kuntz 2
* Corresponding author
1 SYMBIOSE - Biological systems and models, bioinformatics and sequences
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
Résumé : Les hiérarchies binaires orientées ont été introduites pour fournir une représentation graphique orientée d'une famille de règles implicatives d'association. Une telle structure étend d'une façon très spécifique celle sous jacente aux arbres binaires hiérarchiques de classification. Nous proposons ici une formalisation précise de ce nouveau type de structure. Une hiérarchie binaire orientée est définie comme une famille de couples (ordonnés) de parties de l'ensemble à organiser remplissant des conditions spécifiques. Une nouvelle notion d'ultramétricité binaire orientée est construite. le résultat fondamental consiste en la mise en correspondance bijective entre une structure binaire ultramétrique orientée et une hiérarchie binaire orientée. De plus, un algorithme est proposé pour passer de la structure ultramétrique à celle graphique d'un arbre binaire orienté et valué.
Complete list of metadatas

Cited literature [22 references]  Display  Hide  Download

https://hal.inria.fr/inria-00357532
Contributor : Ist Rennes <>
Submitted on : Thursday, February 26, 2009 - 3:59:11 PM
Last modification on : Friday, November 16, 2018 - 1:22:59 AM
Long-term archiving on : Wednesday, September 22, 2010 - 11:34:38 AM

File

PI-1922.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00357532, version 2

Citation

Israël-César Lerman, Pascale Kuntz. Directed binary hierarchies and directed ultrametrics. [Research Report] PI 1922, 2009, pp.21. ⟨inria-00357532v2⟩

Share

Metrics

Record views

375

Files downloads

234