6 Mars - 12 Mars


Retour à la vue des calendrier
Jeudi 9 Mars
Heure: 10:30 - 11:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Catégories de sommets pour le problème de domination
Description: Vincent Bouquet Cette présentation porte sur les sommets qui appartiennent à tous les ensembles dominants minimums d'un graphe. Nous caractérisons ces sommets en fonction de leur criticité relativement au nombre de domination. Cette criticité mesure comment le retrait d'un sommet du graphe affecte le nombre de domination. Nous nous intéressons ensuite à cette caractérisation dans quelques classes de graphes: les graphes triangulés, les cographes, ainsi que des sous-classes des graphes sans griffe. Pour ces graphes, nous montrons que les sommets persistants sont toujours critiques: c'est-à-dire que le retrait d'un sommet persistant fait augmenter le nombre de domination.
Vendredi 10 Mars
Heure: 12:00 - 13:00
Lieu: Visio - https://bbb.lipn.univ-paris13.fr/b/wol-ma9-vjn - 514019
Résumé: Partial Optimality in Cubic Correlation Clustering
Description: Silvia Di Gregorio The higher-order correlation clustering problem is an expressive model, and recently, local search heuristics have been proposed for several applications. Certifying optimality, however, is NP-hard and practically hampered already by the complexity of the problem statement. Here, we focus on establishing partial optimality conditions for the special case of complete graphs and cubic objective functions. In addition, we define and implement algorithms for testing these conditions and examine their effect numerically, on two datasets.