Exposé Bourbaki 1125 : Isomorphismes de graphes en temps quasi-polynomial (d'après Babai et Luks, Weisfeiler-Leman...)
Exposé Bourbaki 1125 : Graph isomorphism in quasipolynomial time (after Babai and Luks, Weisfeiler-Leman...)
Astérisque | Exposés Bourbaki | 2019
Français
Soient donnés deux graphes $\Gamma_1$, $\Gamma_2$ à~$n$ sommets. Sont-ils isomorphes? S'ils le sont, l'ensemble des isomorphismes de~$\Gamma_1$ à $\Gamma_2$ peut être identifié avec une classe $H\cdot\pi$ du groupe symétrique sur~$n$ éléments. Comment trouver $\pi$ et des générateurs de $H$? Le défi de donner un algorithme toujours efficace en réponse à ces questions est resté longtemps ouvert. Babai a récemment montré comment résoudre ces questions - et d'autres qui y sont liées - en temps quasi-polynomial, c'est-à-dire en temps $\exp\left((\log n)^{O(1)}\right)$. Sa stratégie est basée en partie sur l'algorithme de Luks (1980/82), qui a résolu le cas de graphes de degré borné.
Isomorphismes de graphes, isomorphismes de chaînes, configurations cohérentes, designs [sic] combinatoires
Électronique
Prix public
10.00 €
Prix membre
7.00 €
Quantité