Victory du FHCP Challenge : Flinders Hamiltonian Cycle Project

-- Nathann Cohen

Flinders Hamiltonian Cycle Project

The FHCP Challenge organised by the Flinders University (Adelaide, Australia) consisted in a collection of 1001 instances of the Hamiltonian Cycle Problem, ranging in size from 66 vertices up to 9528 vertices, with an average size of just over 3000 vertices. This computational problem is one of the most famous examples of NP-Complete problems, and the selected instances were meant to challenge the known heuristics and lead the participants to design new ones. The team consisting of Nathann Cohen (CNRS/Université Paris-Sud) and David Coudert (INRIA/Université Cote d'Azur) reached 1st place in this competition by finding a Hamiltonian Cycle in 985 instances.

Category: news
Tags: graphs seminar