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.
| 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.
https://hdl.handle.net/11365/4223
Attenzione
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo