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.
|Titolo:||Local search algorithms for finding the Hamiltonian Completion Number of Line Graphs|
|Data di pubblicazione:||2007|
|Digital Object Identifier (DOI):||http://dx.doi.org/10.1007/s10479-007-0231-z|
|Appare nelle tipologie:||1.1 Articolo in rivista|