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.  2001 Elsevier Science B.V. All rights reserved.

Agnetis, A., Detti, P., Meloni, C., Pacciarelli, D. (2001). A linear algorithm for the Hamiltonian completion number of a tree. INFORMATION PROCESSING LETTERS, 79, 17-24 [10.1016/S0020-0190(00)00164-2].

A linear algorithm for the Hamiltonian completion number of a tree

AGNETIS, ALESSANDRO;DETTI, PAOLO;
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 proposed.  2001 Elsevier Science B.V. All rights reserved.
2001
Agnetis, A., Detti, P., Meloni, C., Pacciarelli, D. (2001). A linear algorithm for the Hamiltonian completion number of a tree. INFORMATION PROCESSING LETTERS, 79, 17-24 [10.1016/S0020-0190(00)00164-2].
File in questo prodotto:
File Dimensione Formato  
A linear algorithm for the Hamiltonian completion numberof the line graph of a tree.pdf

non disponibili

Tipologia: Post-print
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 131.99 kB
Formato Adobe PDF
131.99 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: https://hdl.handle.net/11365/4223
 Attenzione

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