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.

Detti, P., & Meloni, C. (2004). A linear algorithm for the Hamiltonian completion number of the line graph of a cactus. DISCRETE APPLIED MATHEMATICS, 136, 197-215 [10.1016/S0166-218X(03)00441-4].

A linear algorithm for the Hamiltonian completion number of the line graph of a cactus

DETTI, PAOLO;
2004

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.
Detti, P., & Meloni, C. (2004). A linear algorithm for the Hamiltonian completion number of the line graph of a cactus. DISCRETE APPLIED MATHEMATICS, 136, 197-215 [10.1016/S0166-218X(03)00441-4].
File in questo prodotto:
File Dimensione Formato  
cactus.pdf

non disponibili

Tipologia: Post-print
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 463.58 kB
Formato Adobe PDF
463.58 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11365/3933
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo