Aller au contenu principal

Christophe Crespelle

Graph editing problems: algorithmic approaches and experimental results on real-world complex networks

2 avril 2021 02:00 PM Paris

In this talk, we consider the problem of modifying the adjacencies of an arbitrary input graph (adding and deleting edges) in order to obtain a graph in a given target class of graphs (i.e. satisfying some properties of interest). Ideally, one would like to be bale to do so using a minimum number of modifications. This problem is usually NP-hard, even for simple target classes. We present some algorithmic approaches to deal with this difficulty of computation, on particular classes of graphs (namely cographs, chordal graphs and ptolemaic graphs), and we highlight some of their possibilities and limitations. We apply some of the algorithms we design on real-world complex networks in order to test how far they are from satisfying some strict mathematical property.

Organisé par

Chef d'équipe : CAPP


Christophe CRESPELLE
Université Claude Bernard Lyon 1
Candidat à un poste de professeur Grenoble INP Ensimag dans CAPP

Publié le 18 mars 2021

Mis à jour le 18 mars 2021