Français Anglais
Accueil Annuaire Plan du site
Accueil > Evenements > Séminaires
Séminaire d'équipe(s) Algorithms and Complexity
Un algorithme exponentiel pour l'étiquetage L(2,1) de graphes
Mathieu Liedloff

25 May 2012, 14:00 - 25 May 2012, 15:00
Salle/Bat : 445/PCRI-N
Contact :

Activités de recherche :

Résumé :
Un étiquetage L(2,1) d'un graphe est une fonction qui,
à chaque sommet, associe un entier positif tel que :
- les étiquettes de sommets adjacents diffèrent d'au moins 2;
- pour tout couple de sommets ayant un voisin commun, leurs
étiquettes soient différentes.

La largeur d'un tel étiquetage L(2,1) est le plus grand entier utilisé
pour étiqueter les sommets. Etant donné un graphe, le problème
d'optimisation demande de calculer un étiquetage L(2,1) de plus
petite largeur possible. Dans cet exposé nous présenterons un
algorithme exponentiel pour résoudre ce problème NP-difficile en
temps $O(2.6488^n)$.

Auteurs: Konstanty Junosza-Szaniawski (Ecole polytechnique de
Varsovie, Pologne), Jan Kratochvil (Université Charles de Prague,
République Tchèque), Mathieu Liedloff (Université d'Orléans,
France), Peter Rossmanith (RWTH Aix-la-Chapelle, Allemagne),
Pawel Rzazewski (Ecole polytechnique de Varsovie, Pologne)

Pour en savoir plus :
Séminaires
Programming computing media (reporté)
Combinatorics
Friday 18 September 2020 - 14:30
Salle : 445 - PCRI-N
Frédéric Gruau .............................................

forum-dev Continuous Integration
Friday 05 June 2020 - 10:00
Salle : 0 - 650
Erik Bray .............................................

Large-scale Spectral Clustering for GPU-based Plat
High-performance computing
Tuesday 24 March 2020 - 10:30
Salle : 465 - PCRI-N
Guanlin He .............................................

Recherche Opérationnelle à Google
Stochastic Combinatorial Optimization
Thursday 12 March 2020 - 14:30
Salle : 445 - PCRI-N
Laurent Perron .............................................

Forum dev-LRI
Wednesday 05 February 2020 - 14:00
Salle : 455 - PCRI-N
Erik Bray .............................................