Local search for Hamiltonian Path with applications to clustering visitation paths

Abstract

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.

Keywords:

• bond energy algorithm (BEA)
• 2-opt
• local search
• clustering a matrix of attributes
• cell formation problems