DAGs et Decompositions des Digraphes – DAGDigDec

Les graphes orientés sont dans l'ensemble beaucoup moins bien compris que les graphes non-orientés, mais reçoivent depuis quelques années une attention de plus en plus soutenues, et des théories de plus en plus profonde commencent à voir le jour. Une notion centrale se dégage de ces travaux: les graphes orientés acycliques, qui sont les graphes orientés ne contenant pas de cycles dirigés (mais ils peuvent contenir des cycles "mal orientés"). Les graphes orientés acycliques jouent un rôle central en mathématique discrète et en informatique. On les retrouve aussi dans de nombreuses applications: télécoms, tries, problèmes d'ordonnancement, compression de données. Comparée à cette omniprésence dans de nombreux domaines, leur compréhension théorique est encore assez pauvre. Ce projet a pour objectif d'étudier la structure et les propriétés des graphes orientés contenant des "grands" sous-graphes orientés acycliques.