Local search for Hamiltonian Path with applications to clustering visitation paths

Clustering a data array has been found useful in the design of web-sites and distributed database system. We show that a critical step during this clustering process is related to solving the Longest Hamiltonian Path Problem, a well-known NP-complete problem. Using the grouping of visitation paths of web-users as a case study, we test several heuristic algorithms. As a result of our experiments, we identify a successful method for dealing with this problem. Our algorithm spends less CPU time and provides better quality solutions than the most recent approach.