Partitionnement d'un ensemble connexe d'hypergraphes orientés sans cycle avec minimisation de chemin - Inria - Institut national de recherche en sciences et technologies du numérique Access content directly
Conference Papers Year : 2022

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

Abstract

Un 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és sans 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.
Partitionnement_dun_ensemble_connexe_dhypergraphes_orientes_sans_cycle_avec_minimisation_de_chemin.pdf (321 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-03596218 , version 1 (03-03-2022)

Identifiers

  • HAL Id : hal-03596218 , version 1

Cite

Julien Rodriguez, François Galea, François Pellegrini, Lilia Zaourar. Partitionnement d'un ensemble connexe d'hypergraphes orientés sans cycle avec minimisation de chemin. 23ème congrès annuel de la Société Française de Recherche Opérationnelle et d'Aide à la Décision, INSA Lyon, Feb 2022, Villeurbanne - Lyon, France. ⟨hal-03596218⟩
95 View
36 Download

Share

Gmail Facebook X LinkedIn More