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.
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
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
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).