ma thèse :

Décomposition modulaire des graphes

   Théorie, extensions et algorithmes


J'ai soutenu ma thèse le 5 décembre 2003 à Montpellier devant le jury composé de MM.

Télécharger le manuscript en format ps pdf

o Résumé

La première partie de cette thèse, théorique, concerne des familles de parties d'un ensemble possédant les même propriétés que les modules d'un graphes : les familles partitives. On s'intéresse à des généralisations de la décomposition modulaire des graphes. La famille des 2-modules est étudiée.
Puis sont exposées les décomposition en 2-joints, en sesquimodules, et la décomposition bimodulaire des graphes bipartis, parallèle presque complet dans le cas biparti de la décomposition modulaire, qui se calcule polynômialement.

Enfin la seconde partie, pratique, présente des algorithmes de décomposition modulaire en O(n+m) pour le cas des graphes non-orientés, des tournois, et des graphes orientés, et en O(n) pour les graphes d'intervalles et les graphes de permutation. Tous ces algorithmes sont linéaires en la taille de la donnée; les deux premiers sont plus simples que les algorithmes existants; et les trois derniers atteignent cette borne pour la première fois.
 

o Mots-clef

Graphes, algorithmes, décomposition modulaire, modules, familles partitives, 2-modules, 2-joints, graphes bipartis, graphes d'intervalles, graphes de permutation

o Abstract


The first part of this thesis is devoted to theory. First it is question of set decompositions that have the same properties than modular decomposition: the partitive families.  Then are presented some graph decompositions that extend modular decomposition, using the notion of 2-modules (homogeneous pairs). This is the case for the split decomposition of Cunningham, and also for the new 2-joins and sesquimodules decompositions. A analog of modules
for bipartites graphs, the bimodules, leads to a decomposition theory very near the modular decomposition of directed graphs.

The second part is practical and presents modular decompositions algorithms for undirected graphs, tournaments, directed graphs, interval graphs and permutation graphs. All these algorithms run in linear-time from the input: O(n+m) for the three first classes, O(n) for the two last classes. The tree last algorithms reach linearity for the first time.
 

o Keywords

Graphs, algorithms, modular decomposition, modules, homogeneous sets, partitive set families, 2-modules, homogeneous pairs, 2-joins, bipartite graphs, interval graphs, permutation graphs