Local search algorithms for finding the Hamiltonian completion number of line graphs |
| |
Authors: | Paolo Detti Carlo Meloni Marco Pranzo |
| |
Institution: | (1) Dipartimento di Ingegneria dell’Informazione, Università di Siena, Siena, Italy;(2) Dipartimento di Elettrotecnica ed Elettronica, Politecnico di Bari, Bari, Italy |
| |
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
-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. |
| |
Keywords: | Hamiltonian completion number Dominating trail set Local search Graph algorithms Line graphs |
本文献已被 SpringerLink 等数据库收录! |
|