VNS pour le Minimum Sitting Arrangement Problem

Session : GR / Graphes
Jeudi 11 février 15:00 - 16:40 Salle : RP13
Alban Derrien, Borja Menéndez, Marc Sevaux, Eduardo Pardo et Abraham Duarte

Les graphes signés sont des graphes pour lesquels les arêtes ont un signe positif ou négatif. En psychologie sociale, les graphes signés modélisent des relations sociales. Les arêtes positives présentent alors l’amitié et les arêtes négatives les inimitiés entre les nœuds qui représentent les personnes. Dans un travail récent, Kermarrec et al. ont formalisé le problème suivant : « Est il possible de dessiner un graphe signé tel que pour toutes personnes, ses amis sont plus proches que ses ennemis ? ». Dans ce travail, nous avons étudié différentes approches du VNS pour résoudre ce problème. Le travail préliminaire que nous avons effectué montre que cette approche est très prometteuse.

Mots clés : graphe, réseaux sociaux, sitting arrangement, métaheuristiques, VNS