Résumé | Dans cet exposé je présenterai une structure de données compacte permettant de calculer en temps constant la distance entre n'importe quelle paire de sommets d'un graphe arbitraire à n sommets. Cette structure de données se présente sous forme d'étiquette associée à chacun des sommets, la distance entre les u et v étant décodée à partir d'un calcul impliquant seulement les étiquettes de u et de v. Cet exposé sera l'occasion de vous parler de la Squashed Cube Dimension, du Theorème de Fleishner et d'Hamiltonisme. Ce travail est en collaboration, entre autre avec un certain Petersen.
|