𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Local search algorithms for finding the Hamiltonian completion number of line graphs

✍ Scribed by Paolo Detti; Carlo Meloni; Marco Pranzo

Publisher
Springer US
Year
2007
Tongue
English
Weight
409 KB
Volume
156
Category
Article
ISSN
0254-5330

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

A linear algorithm for the Hamiltonian c
A linear algorithm for the Hamiltonian completion number of the line graph of a cactus
✍ Paolo Detti; Carlo Meloni πŸ“‚ Article πŸ“… 2004 πŸ› Elsevier Science 🌐 English βš– 464 KB

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 ΓΏnding HCN (L(G)) when G