Local search algorithms for finding the Hamiltonian completion number of line graphs

Local search algorithms for finding the Hamiltonian completion number of line graphs

0.00 Avg rating0 Votes
Article ID: iaor20084069
Country: Netherlands
Volume: 156
Issue: 1
Start Page Number: 5
End Page Number: 24
Publication Date: Dec 2007
Journal: Annals of Operations Research
Authors: , ,
Keywords: heuristics: local search
Abstract:

Given a graph G=(V,E), the Hamiltonian completion number of G, HCN(G), is the minimum number of edges to be added to G to make it Hamiltonian. This problem is known to be NP-hard even when G is a line graph. In this paper, local search algorithms for finding HCN(G) when G is a line graph are proposed. The adopted approach is mainly based on finding a set of edge-disjoint trails that dominates all the edges of the root graph of G. Extensive computational experiments conducted on a wide set of instances allow to point out the behavior of the proposed algorithms with respect to both the quality of the solutions and the computation time.

Reviews

Required fields are marked *. Your email address will not be published.