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(vertical bar V vertical bar + vertical bar E vertical bar) 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.
|Autori interni:||MELONI, Carlo|
|Titolo:||A lower bound on the Hamiltonian path completion number of a line graph|
|Rivista:||APPLIED MATHEMATICS AND COMPUTATION|
|Data di pubblicazione:||2013|
|Digital Object Identifier (DOI):||10.1016/j.amc.2013.06.020|
|Appare nelle tipologie:||1.1 Articolo in rivista|