Sur quelques généralisations polynomiales de la décomposition modulaire
Institution:
Paris 7Disciplines:
Directors:
Abstract EN:
Modular decomposition is a graph decomposition extensively studied since its introduction in 67 by Gailai. This decomposition appears to be a powerful tool from both theoretical and algorithmic point of view. In this thesis we will deal with both of them. We present two generalizations of modular decomposition and we Systematize the use of a well known algorithmic technique, partition refinement, to solve the probtem raised by these generalizations. The thesis is divided into two parts, The first par is dedicated to the introduction and the study of the generalizations of modular decomposition. To do so, we introduce a new discrete structure» "homogeneous relations" which abstract the notion of neighbourhood to conserve only the essential notion of distinction. We study combinatorics properties of modular decomposition on this structure and we provide efficient algorithms to compute this decomposition. We then introduce a new decomposition, the "umodular" decomposition. It is to consider the dual point of view from modular decomposition. The second part presents algorithms to solve the following problems. The first problem is, given a family of subsets of a finite set, find efficiently the overlap components of this family. We present an algorithm due to Dahlhaus, and we simplify its approach, by replacing a complex and tedious algorithmic technique using partition refinement. Algorithms obtained are linear. The second problem is to recognize graph of NLC width 2. We present a S0(n ^2m)S algorithm and we provide a technique to test in the same complexity isomorphism of NLC-2 graphs.
Abstract FR:
La décomposition modulaire est une décomposition de graphes très étudiée depuis son introduction en 67 par Gallai. Cette décomposition s'est montrée être un outils très puissant tant d'un point de vue théorique que d'un point de vue algorithmique. Dans cette thèse nous abordons ces deux aspects. Nous proposons deux généralisations de la décomposition modulaire et nous systématisons l'usage d'une technique très connue en algorithmique, l'affinage de partitions, pour résoudre les problèmes soulevés par ces généralisations. Le mémoire se divise en deux parties, la première partie est consacrée à l'introduction et l'étude de deux généralisations de la décomposition modulaire. Pour ce faire, nous introduisons une nouvelle structure discrète: les "relations homogènes" qui abstrait la notion de voisinage pour ne retenir que la notion essentielle de distinction. Nous étudions les propriétés comminatoires de la décomposition modulaire sur cette structure et nous présentons des méthodes pour calculer cette décomposition efficacement. Ensuite, nous introduisons une nouvelle décomposition, la décomposition en "umodules". H s'agit d'adopter le point de vue dual de la décomposition modulaire. La seconde partie présente des algorithmes efficaces pour résoudre les deux problèmes suivants. Le premier problème consiste à trouver les composantes de chevauchement d'une famille de partie d'un ensemble fini. Nous présentons un algorithme dû à Dahlhaus et simplifions ce dernier en remplaçant une procédure complexe par une technique d'affinage de partition. Le second algorithme reconnaît les graphes de largeur Nlc-2 en temps S0(n ^2m)S et fournit une méthode de même complexité pour résoudre le problème de l'isomorphisme sur cette classe.