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 a O(|V|) algorithm exists when G is a tree. In this paper a linear algorithm for finding HCN(L(G)) when G is a cactus is proposed.
|Titolo:||A linear algorithm for the Hamiltonian completion number of the line graph of a cactus|
|Data di pubblicazione:||2004|
|Digital Object Identifier (DOI):||http://dx.doi.org/10.1016/S0166-218X(03)00441-4|
|Appare nelle tipologie:||1.1 Articolo in rivista|