|
|
 |
|
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. |
|
|
