Partitionnement d'un ensemble connexe d'hypergraphes orientés sans cycle avec minimisation de chemin

International audienceUn hypergraphe est une extension de la notion de graphe dans lequel les hyperarêtes contiennent au moins un sommet. Les hypergraphes modélisent de nombreux objets comme par exemple, un circuit électronique, un ensemble de données ou un ensemble de tâches/calculs à réaliser. Le partitionnement d'un hypergraphe consiste à séparer les sommets en plusieurs sous-ensembles appelés parties, de taille plus ou moins similaire. L'objectif est de minimiser le nombre d'hyperarêtes partagées entre les parties. Dans ce travail, nous nous intéressons au problème de partitionnement sur une sous-classe d'hypergraphes modélisant des circuits électroniques. Ces hypergraphes sont composés de sous-hypergraphes orientés sans cycles, inter-connectés par les sommets sources et les sommets puits de ces derniers. Nous proposons aussi d'étendre la fonction objectif mesurant le coût de coupe afin tenir compte de la minimisation de la longueur des chemins au sein des sous-hypergraphes orientéssans cycle. Dans notre contexte, une hyperarête coupée sera pénalisée et augmentera la longueur des chemins incluant cette dernière. Afin de traiter ce problème nous proposons dans cette étude de comparer deux méthodes basées sur une approche multi-niveaux