| Titre : | Décomposition Modulaire des Graphes, Théorie, Extensions et Algorithmes | | Type de document : | texte imprimé | | Auteurs : | F. DEMONTGOLFIER, Auteur | | Année de publication : | 2003 | | Langues : | Français (fre) | | Tags : | GRAPHES ALGORITHMES DECOMPOSITION MODULAIRE FAMILLES PARTITIVES 2-MODULES 2-JOINTS GRAPHES BIPARTIS GRAPHES D'INTERVALLES GRAPHES DE PERMUTATION MODULAR DECOMPOSITION OF GRAPHS. THEORY EXTENSIONS AND ALGORITHMS. GRAPHS ALGORITHMS MODULAR DECOMPOSITION PARTITIVE SET FAMILIES2-MODULES HOMOGENEOUS PAIRS 2-JOINS BIPARTITE GRAPHS INTERVAL GRAPHS PERMUTATION GRAPHS | | Index. décimale : | THE Thèses de doctorat | | 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écompositions 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.
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. | | Directeur(s) de thèse : | HABIB M. | | Co-directeur(s) de thèse : | PAUL C. | | Président du jury : | CROCHEMORE M. | | Rapporteur(s) : | McCONNELL R.M.;VANHERPE J.M.;GAVOILLE C. | | Examinateur(s) : | FOUQUET J.L. | | Date de soutenance : | 05/12/2003 |
Décomposition Modulaire des Graphes, Théorie, Extensions et Algorithmes [texte imprimé] / F. DEMONTGOLFIER, Auteur . - 2003. Langues : Français ( fre) | Tags : | GRAPHES ALGORITHMES DECOMPOSITION MODULAIRE FAMILLES PARTITIVES 2-MODULES 2-JOINTS GRAPHES BIPARTIS GRAPHES D'INTERVALLES GRAPHES DE PERMUTATION MODULAR DECOMPOSITION OF GRAPHS. THEORY EXTENSIONS AND ALGORITHMS. GRAPHS ALGORITHMS MODULAR DECOMPOSITION PARTITIVE SET FAMILIES2-MODULES HOMOGENEOUS PAIRS 2-JOINS BIPARTITE GRAPHS INTERVAL GRAPHS PERMUTATION GRAPHS | | Index. décimale : | THE Thèses de doctorat | | 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écompositions 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.
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. | | Directeur(s) de thèse : | HABIB M. | | Co-directeur(s) de thèse : | PAUL C. | | Président du jury : | CROCHEMORE M. | | Rapporteur(s) : | McCONNELL R.M.;VANHERPE J.M.;GAVOILLE C. | | Examinateur(s) : | FOUQUET J.L. | | Date de soutenance : | 05/12/2003 |
|
Affiner la recherche Interroger des sources externesDécomposition Modulaire des Graphes, Théorie, Extensions et Algorithmes / F. DEMONTGOLFIER
