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. - 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

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
Algorithms; Hamiltonian path; Hamiltonian completion number; tree; line graph
01 Pubblicazione su rivista::01a Articolo in rivista
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. - 79:1(2001), pp. 17-24. [10.1016/S0020-0190(00)00164-2]
File allegati a 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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1583457
 Attenzione

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

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 13
  • ???jsp.display-item.citation.isi??? 11
social impact