Distance d'édition minimum à un linegraph
Résumé
On se propose dans cette présentation d'étudier le problème de la distance d'édition entre un graphe et l'ensemble des linegraphs. Un linegraph ou graphe des arêtes est un graphe non orienté obtenu à partir d'un autre graphe non orienté. Connaissant un graphe G = (V, E) (simple ou non), le linegraph de G est un graphe H simple possédant un nœud ve pour chaque arête e de G et une arête relie ve et vf si les arêtes e et f sont incidentes au même nœud dans G. Cette définition peut se généraliser aux hypergraphes, où chaque nœud de H représente une hyperarête et chaque arête indique si deux hyperarêtes ont une intersection non vide. La distance d'édition est une mesure classique utilisée pour mesurer la proximité d'un graphe non orienté à un autre graphe ou une classe de graphes (comme exemple de classe, on peut citer les graphes planaires, les linegraphs, les graphes sans diamant induit, . . .). La distance est le nombre minimum de corrections qu'il faut apporter à un graphe pour que le graphe résul- tat appartienne à la classe en question. Les corrections sont de natures variées. On considère généralement l'ajout et la suppression d'arêtes ou de nœuds. Ce problème a été abondamment étudié pour de nombreuses classes, notamment sa complexité paramétrée vis-à-vis de la dis- tance recherchée [1]. Dans cette étude on s'intéressera à la classe des linegraphs et à l'ajout et la suppression d'arêtes.
Origine : Fichiers produits par l'(les) auteur(s)