| Title | Transformations de graphes et réductions pseudobooléennes |
| Speakers | DE WERRA, Dominique (École Polytechnique Féderale de Lausanne, Suisse) |
| Date | Tuesday, September 16, 2008 |
| Time | 10h45 AM |
| Place | Salle 6516, Pavillon André-Aisenstadt Campus de l'Université de Montréal 2920, chemin de la Tour |
|
Abstract Des transformations de graphes ont été élaborées soit pour réduire d’une quantité donnée le nombre de stabilité d’un graphe, soit pour diminuer le nombre d’arêtes ou de sommets sans changer le nombre de stabilité. Certaines de ces transformations ont été inspirées par des formulations pseudobooléennes du problème de la recherche d’un ensemble stable de taille maximum. Il est apparu que certaines de ces transformations ont des liens très directs avec des opérations de fusion de sommets utilisées pour les graphes parfaits. Nous examinerons certaines de ces réductions dont celle dite de l’aimant et mettrons en évidence des connexions avec des extensions des couples de sommets liés uniquement par des chaines induites de longueur paire (de tels sommets sont appelés amis). Des questions ouvertes sur l’interprétation des réductions dans le cas de classes particulières de graphes parfaits seront présentées. |
|
| Organizer | Alain Hertz (alain.hertz@gerad.ca) |