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

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

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

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

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