Abstract of PhD thesis - Alain Sigayret - december 20th, 2002.
→ Cette page en franšais
Back to publication list
We propose a new approach, which uses graphs, for two data analysis problems.

Phylogeny:
We use the threshold family of graphs associated with a dissimilarity to define a new distance, more general than an additive tree distance, which we call triangulated distance. We introduce the new concept of maximal sub-triangulation, consistent with the fact that phylogenetic values tend to be too low. We then propose an algorithm ajusting data to a triangulated distance, by sub-triangulating associated graphs.

Formal Concept Analysis:
We encode a finite binary relation R and its Concept Lattice L(R) by an undirected co-bipartite graph G(R). We show that there is a one-to-one correspondence between the elements of L(R) and the minimal separators of G(R), and a one-to-one correspondence between the maximal paths in L(R) and the minimal triangulations of G(R). Thus, algorithmic processes for G(R) leads us to correspondind processes for L(R). For instance, polynomial-sized lattices can be obtained from L(R), by embeding G(R) in a weakley triangulated graph.
Next, we show that there is a domination partial ordering on maximal clique modules of G(R). This domination is inherited from an element to another during the traversal of a maximal path of L(R). We deal dynamically with domination relationships using a data structure we called domination table.
We use this table for two algorithmic problems:
- Maintaining a Galois sub-hierarchy, in the context of inheritance for object-oriented languages;
- Efficient Generation of a Concept Lattice.

Keywords: Algorithms, Graphs (triangulated, weakley triangulated, triangulation), Galois lattices, Formal Concept Analysis, Domination order, Galois hierarchies, Phylogeny, Distances (triangulated).