Blanc SIMI 2 - Blanc - SIMI 2 - Science informatique et applications

Structures Interdites – Stint

Résumé de soumission

Les sous-graphes induits jouent un rôle central dans la théorie des graphe, tant dans ses aspects structurels qu'algorithmiques. Un graphe H est un sous-graphe induit d'un graphe G si on peut obtenir H à partir de G en enlevant des sommets. Parmi toutes les notions de sous-graphes, celle-ci est la plus forte, et de ce fait être sans-H (c'est-à-dire ne pas contenir H en tant que sous-graphe induit) n'est pas très restrictif. Des notions plus faibles de sous-graphes, comme par exemple la notion de mineur de graphe, est maintenant bien comprise, et la prochaine étape de la théorie des graphes est sans doute la compréhension de l'exclusion de structures induites. La question centrale de notre projet est la suivante :

Etant donné une famille (éventuellement infinie) F de graphes, quelles sont les propriété d'un graphe sans aucun sous-graphe induit membre de F ?

Cette question est la clef de nombreux problèmes, car beaucoup de classes de graphes importante sont définies par sous-graphes induits exclus. Ce domaine est actuellement en croissance rapide, et des techniques et outils se développent aujourd'hui.

Notre premier but est d'établir des bornes sur plusieurs paramètres classiques pour les graphes sans-F, comme par exemple le nombre de clique, le nombre de stabilité et le nombre chromatique. Un second but est de concevoir des algorithmes efficaces pour décider si un graphe est sans-F et de calculer ou d'approximer des paramètres. Nous envisageons aussi d'étudier la contrepartie de toutes ces notions dans le cas orienté.

A cette fin, nous proposons d'utiliser et de développer différentes techniques de preuve, parois récentes, comme la description structurelle des classes de graphes, le lemme de régularité, les limites de graphes, les algèbre de drapeau, la VC-dimension, le déchargement ainsi que les preuves assistées par ordinateur.

Coordinateur du projet

Monsieur Nicolas TROTIGNON (Laboratoire de l'Informatique du Parellélisme, Lyon)

L'auteur de ce résumé est le coordinateur du projet, qui est responsable du contenu de ce résumé. L'ANR décline par conséquent toute responsabilité quant à son contenu.

Partenaire

LIP Laboratoire de l'Informatique du Parellélisme, Lyon
I3S-CNRS Laboratoire d'Iformatique, Signaux et Systèmes de Sophia-Antipolis
G-SCOP Laboratoire des Sciences pour la Conception, l'Optimisation et la Production de Grenoble

Aide de l'ANR 336 346 euros
Début et durée du projet scientifique : décembre 2013 - 48 Mois

Liens utiles

Explorez notre base de projets financés

 

 

L’ANR met à disposition ses jeux de données sur les projets, cliquez ici pour en savoir plus.

Inscrivez-vous à notre newsletter
pour recevoir nos actualités
S'inscrire à notre newsletter