|
Archives année 2001-2002 |
Mon exposer va consister à démontrer la NP-complétude des 3 problèmes suivants (ou juste de 2, ou juste de 1 suivant le temps de réceptivité de mon auditoire)~:
D'après le livre de V.V. Vazirani, Approximation
Algorithms
Comment peut-on établir une garantie d'approximation pour un
algorithme sans connaître la solution optimale au problème concerné
(problème NP-dur) ? Une solution classique consiste à rechercher une
borne inférieure calculable en temps polynomial.
Nous aborderons 3 problèmes utilisant des techniques algorithmiques
différentes :
Un couplage induit de G est un sous-graphe de G de la forme c.K2 (2c sommets de degré 1 et c arrêtes). Il s'agit de maximiser c. Selon la classe de graphes considéré, le problème est P ou NP. Pour convaincre tous mes auditeurs potentiels de l'intérêt de la chose, une liste de problèmes pratiques (?), dont il s'agit de déterminer si la solution est P ou NP, est accessible par un click.
D'après l'article de M. Chrobak et D. Eppstein, Planar
Orientations with Low Out-Degree and Compaction of Adjacency
Matrices
Nash-Williams a montré que les arêtes d'un graphe planaire peuvent
être partitionnées en 3 forêts. Cet article présente 3 algorithmes
pour calculer une telle partition. Le premier nécessite un
plongement du graphe dans le plan, le second s'en passe. Tout deux
ont une complexité linéaire. Le troisième est un algorithme
parallèle pour ce problème.
Un résumé des résultats présentés
est disponible (attention : ce texte n'est pas complètement
stable).
Un circuit intégré peut etre vu comme un graphe. Pour tester la correction d'un circuit intégré, il est nécessaire de pouvoir réinitialiser l'ensemble de ce circuit. Pour cela, nous sommes ramener à calculer un coupe cycle dans un graphe. Le problème du calcul d'un coupe cylce minimum est approximable. Nous présenterons un algorithme probabiliste glouton pour ce problème.
D'après l'article Algorithms and Complexity of Sandwich problems in
Graphs de Golumbic, Kaplan et Shamir.
Soient G1 et G2 deux graphes définis sur le même
ensemble V de sommets tels que E1 est inclus dans
E2. Le "sandwich problem" pour la propriété P consiste à
tester s'il existe un graphe G=(V,E) tel que E1 inclus dans
E et E inclus dans E2. L'article fait une synthèse sur les
propriétés pour lesquelles ce problème est polynomial, NP-Complet.
Un étiquetage des distances pour un graphe est une affectation
d'étiquettes à chaque sommet du graphe de telle sorte que la distance
entre 2 sommets quelconques puissent être calculée ou approximée en
n'utilisant que leurs étiquettes.
Une famille de graphes possède un étiquetage implicite des distances
si le nombre de graphes à n sommets de la famille est 2f(n)
et que la taille des étiquettes utilisées est en O(f(n)/n). La famille des
graphes d'intervalles est la seule famille connue possédant un
étiquetage implicite des distances. De manière surprenante cet
étiquetage fait appel à une représentation des graphes de
permutation.
L`exposé sera un résumé de deux articles sur le Codage du graphe du Web .
L'exposé sera une présentation du chapitre d'introduction du livre
Intersection Graph Theory de T. McKee et FR. McMorris. Nous
présenterons des propriétés générales sur les graphes d'intersections
ainsi que quelques problèmes ouverts.
Un résumé des résultats présentés est disponible
(attention : ce texte n'est pas complètement stable).