Directed binary hierarchies and directed ultrametrics

Israël-César Lerman 1 Pascale Kuntz 2
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é.
Document type :
Reports
Complete list of metadatas

https://hal.inria.fr/inria-00357532
Contributor : Agnès Hermann <>
Submitted on : Friday, January 30, 2009 - 3:54:28 PM
Last modification on : Thursday, November 15, 2018 - 11:57:19 AM
Long-term archiving on: Tuesday, June 8, 2010 - 9:44:41 PM

File

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

Identifiers

  • HAL Id : inria-00357532, version 1

Collections

Citation

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

Share

Metrics

Record views

30

Files downloads

4