Given a line graph L(G) of a graph G=(V,E), the problem of finding the minimum number of edges to add to L(G) to have a Hamiltonian path on L(G) is considered. This problem, related to different applications, is known to be NP-hard. This paper presents an O(|V|+|E|) algorithm to determine a lower bound for the Hamiltonian path completion number of a line graph. The algorithm is based on finding a collection of edge-disjoint trails dominating all the edges of the root graph G. The algorithm is tested by an extensive experimental study showing good performance suggesting its use as a building block of exact as well as heuristic solution approaches for the problem.
Scheda prodotto non validato
Scheda prodotto in fase di analisi da parte dello staff di validazione
|Titolo:||A lower bound on the Hamiltonian path completion number of a line graph|
|Citazione:||Detti, P., Meloni, C., & Pranzo, M. (2013). A lower bound on the Hamiltonian path completion number of a line graph. APPLIED MATHEMATICS AND COMPUTATION, 220, 296-304.|
|Appare nelle tipologie:||1.1 Articolo in rivista|
File in questo prodotto: