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
A linear algorithm for the hamiltonian completion number of the line graph of a tree / Agnetis, A.; Detti, P.; Meloni, C.; Pacciarelli, D.. - In: INFORMATION PROCESSING LETTERS. - ISSN 0020-0190. - STAMPA. - 79:1(2001), pp. 17-24. [10.1016/S0020-0190(00)00164-2]
A linear algorithm for the hamiltonian completion number of the line graph of a tree
Meloni, C.;
2001-01-01
Abstract
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 proposedFile in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
