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.
A linear algorithm for the Hamiltonian completion number of the line graph of a cactus / Detti, P.; Meloni, C. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - STAMPA. - 136:2-3(2004), pp. 197-215. (Intervento presentato al convegno ctw 2001 tenutosi a Colonia) [10.1016/S0166-218X(03)00441-4].
A linear algorithm for the Hamiltonian completion number of the line graph of a cactus
Meloni, C
2004-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 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.File 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.
