Le défi des 1001 graphes

Nathann Cohen (1) , David Coudert (2)

1 GALaC - LRI - Graphes, Algorithmes et Combinatoire (LRI)
2 COATI - Combinatorics, Optimization and Algorithms for Telecommunications

Dans un graphe, existe-t-il un circuit visitant chaque sommet une fois et une seule ? Une question difficile pour certains graphes... Cet article explique comment les auteurs ont abordé et remporté la compétition internationale organisée par la Flinders University d'Adelaïde (Australie), intitulée FHCP Challenge, sur le problème du cycle hamiltonien dans les graphes.

Mots clés: théorie des graphes; cycle hamiltonien; algorithmes

Domaines: Algorithme et structure de données [cs.DS]; Mathématique discrète [cs.DM]

Nathann Cohen, David Coudert. Le défi des 1001 graphes. Interstices, 2017. ⟨hal-01662565⟩