Lifo - Laboratoire d'Informatique Fondamentale d'orléans Université d'Orléans université d'Orléans ENSI Bourges ENSI Bourges

Lifo > GAMoC : Graphes, Algorithmes et Modèles de Calcul

English Version



Contact

LIFO - Bâtiment IIIA
Rue Léonard de Vinci
B.P. 6759
F-45067 ORLEANS Cedex 2

Tel: +33 (0)2 38 41 70 11
Fax: +33 (0)2 38 41 71 37



GAMoC : Graphes, Algorithmes et Modèles de Calcul

Professeur

Maître de Conférences HDR

Maître de Conférences

Doctorant

Professeur Emerite

Chercheur - autre statut

Domaines de Recherche

  • Combinatoire des graphes cubiques.

  • Algorithmes exacts pour le résolution de problèmes NP-difficiles.

Combinatoire des graphes cubiques

Le fameux théorème des 4 couleurs (quel que soit le découpage d’un pays, la carte de ses départements ou régions peut être coloriée avec au plus 4 couleurs ou, plus formellement, tout graphe planaire est 4-coloriable) a mis les graphes cubiques au centre de nombreuses recherches en théorie des graphes. Un graphe est cubique si chaque sommet a exactement trois voisins. Il est équivalent de montrer que tout graphe planaire est 4 coloriable ou bien que tout graphe cubique planaire a ses arêtes coloriables en 3 couleurs. Même si le théorème des 4 couleurs est maintenant prouvé, il a donné lieu a de nombreuses conjectures, toujours ouvertes, sur les graphes cubiques (conjecture des 5-flots de TUTTE, conjecture de FULKERSON, conjecture de FAN et RASPAUD). La problématique générale envisagée dans cette famille de conjectures est la couverture minimale en couplages parfaits d’un graphe cubique sans isthme (un graphe cubique 3-coloriable est optimal en ce sens).

Les conjectures évoquées ci-dessus sont des généralisations envisageables du théorème des 4 couleurs et des tentatives d’en trouver une preuve qui ne fasse pas appel à un examen exhaustif de configurations via un ordinateur. Nous avons travaillé sur les partitions linéaires des graphes cubiques (c.-à-d. partition de l’ensemble d’arêtes forêts linéaires, dont les composantes connexes sont des chaînes) et sur une nouvelle notion de partition normale. Nous avons apporté de nouvelles caractérisations des graphes cubiques 3-arête-coloriables ainsi qu’un théorème de structure permettant d’assurer l’existence d’une couverture en 6 couplages parfaits correspondant à la conjecture de Fulkerson dans certaines familles de graphes cubiques sans isthme.

Signalons également des travaux sur des problèmes extrémaux et sur des graphes avec configurations exclues.

Algorithmes exacts pour la résolution de problèmes NP-difficiles

En algorithmique exacte on souhaite calculer une solution optimale à un problème d’optimisation NP-difficile ; les algorithmes conçus sont donc exponentiels, l’objectif étant néanmoins d’obtenir la meilleure complexité possible. Ce domaine est en pleine expansion et l’on peut évoquer au moins deux bonnes raisons pour cela. Sur le plan pratique, il est souvent important de donner une solution exacte à la question posée et ne pas se contenter d’une solution approchée (c’est typiquement le cas des problèmes d’allocations de ressources lorsque ces ressource sont chères). Or avec la puissance de calcul actuelle, des algorithmes exponentiels de complexité modérée peuvent s’avérer efficaces sur des données de taille moyenne. Sur le plan théorique, la question : à quel point peut-on réduire le temps de résolution d’un problème combinatoire fini par rapport à une simple exploration par force brute de toutes les possibilités ? est au coeur de la complexité ; on trouve son origine dans une célèbre lettre adressée, en 1956, par Gödel à von Neumann.

Une approche très générale (et fortement développée dans notre équipe) pour la résolution des problèmes difficiles porte sur les décompositions de graphes. Pour les graphes que l’on peut décomposer en petits morceaux qui s’agencent selon des règles simples, de nombreux problèmes d’optimisation (NP-difficiles dans le cas général) peuvent être résolus efficacement grâce à la décomposition. Plus spécifiquement, ces algorithmes auront une complexité exponentielle non pas en la taille du graphe, mais en la taille des morceaux de la décomposition, ce dernier paramètre étant appelé largeur de la décomposition. Nous avons travaillé sur le calcul de décompositions arborescentes et de décompositions linéaires optimales ou proches de l'optimum.

Nous sommes également en pointe sur l'utilisation et l'amélioration de techniques très récentes pour la conception et l'analyse des algorithmes exact, comme mesurer et conquérir pour les algorithmes de branchement, la compression itérative, la convolution, etc. Nous avons contribué à l'introduction d’une nouvelle technique appelée branchement et rechargement, actuellement utilisée pour certains types de problèmes de domination, mais qui a vocation à être généralisée.

Notons que cette thématique de recherche est au coeur du programme ANR AGAPE (Algorithmes de Graphes A Paramètre fixe et Exacts) qui inclut cinq membres de l’équipe et deux membres de l'équipe SDS.

Modèles continus de calcul

La dernière décennie a vu l'émergence de modèles de calcul s'éloignant tout ou partie du cadre classique du calcul et de la thèse de Church-Turing (modèles se basant sur les réels ou hypercomputing avec des machines de Turing à temps infini). Nous avons introduit et étudié un modèle appelé Abstract Geometrical Computation, modèle de machine à signaux trouvant son origine dans les automates cellulaires. Ici la notion de signal (discret) est déplacée dans un cadre où le temps comme l'espace sont continus. Ce modèle sort de la théorie classique de la récursivité par la nature des positions et des dates, qui correspondent a priori à des nombres réels. Nous avons montré que ces machines à signaux permettent d’implanter le modèle BSS ainsi que l’analyse récursive (machines de Turing de type 2, où les réels sont représentés par des suites convergentes d’approximations). Actuellement nous étudions les fractales (naturellement engendrées par le modèle) afin de les utiliser pour positionner des sous-calculs.

Nous nous ouvrons à l’auto-assemblage de tuiles. L’étude de ce modèle repose sur des signaux discrets et la synergie avec les machines à signaux est naturelle.

Projets de recherche pour l'équipe GA

Nous poursuivrons les études menées sur la famille des graphes cubiques et nous développerons de nouveaux thèmes émergents, à savoir l’étude des graphes (H; k)-stables (notion assez récemment introduite) ainsi que des travaux autour de la complémentation de Seidel.

Nous continuerons à travailler sur l’amélioration et l’application des outils pour l'algorithmique exacte, dont nous sommes parmi les bons connaisseurs. Les méthodes mesurer pour conquérir, celles qui utilisent des décompositions arborescentes ou la très récente technique de branchement et rechargement feront clairement partie de nos sujets de recherche à moyen terme, et nous espérons en ajouter d’autres à la liste.

La problématique des modèles de calcul continus laisse également ouvertes de nombreuses perspectives, comme le lien entre les phénomènes d'accumulation et la hiérarchie arithmétique, ou les ponts entre le modèle de machine à signaux continus et d'autres modèles de calcul. Nous nous intéressons aussi aux constructions qui peuvent être automatiquement traduites dans le monde des automates cellulaires tout en conservant certaines propriétés.

Enfin, nous nous intéressons à l'algorithmique des réseaux d'interconnexion, en particulier à des aspects dynamiques et de complexité de communication dont l'étude combine des outils de graphes et d'automates cellulaires.

Collaborations et animation de la recherche

Collaborations internationales

Nous avons des rapports privilégiés avec l'Université de Bergen (Norvège), l'Université des Mines et de la Métallurgie (AGH) de Cracovie (Pologne) et l'Université du Chili (Santiago, Chili). Ces collaborations ont ont donné lieu à des visites, dans les deux sens, de doctorants et de chercheurs permanents, notamment dans le cadre de programmes internationaux EGIDE et ECOS, ainsi qu'à des accords ERASMUS.

Animation

Participation aux projets

  • ANR AGAPE : Algorithmes de Graphes à Paramètre Fixe et Exacts (programme blanc, 2009-2013)
  • PEPS GraphIQ Projet Exploratoire Pluridisciplinaires soutenu par l’INS2I : Informatique quantique et théorique des graphes : étude des états graphes (GraphIQ, 2010-2011)
  • Partenariat franco-chilien ECOS-Concyt : Réalisation de graphes avec contraintes de degrés (2010-2012)
     
  • ANR blanc Stratégie et algorithmes pour la décomposition et la résolution de problèmes d’optimisation sous contraintes (STAL-DEC-OPT, 2005-2008)
  • Partenariats franco-norvégiens PHC EGIDE-Aurora sur les séparateurs minimaux et les décompositions arborescentes (2004-2006 et 2008-2009)
  • Partenariats franco-chiliens ECOS-Conicyt : Pavages : flips et auto-assemblages (2005-2008)

Actions de recherche en cours