A linear algorithm for the Hamiltonian completion number of the line graph of a tree
Given a graph G = (V, E), HCN(L(G)) is the minimum number of edges to be added to its line graph L(G) to make L(G) Hamiltonian. This problem is known to be NP-hard for general graphs, whereas an O(/V/(5)) algorithm exists when G is a tree. In this paper a linear algorithm for finding HCN(L(G)) when G is a tree is proposed. (C) 2001 Elsevier Science B.V. All rights reserved.
algorithms hamiltonian completion number line graph tree hamiltonian path