Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6421883 | Applied Mathematics and Computation | 2013 | 9 Pages |
Abstract
Given a line graph L(G) of a graph G=(V,E), the problem of finding the minimum number of edges to add to L(G) to have a Hamiltonian path on L(G) is considered. This problem, related to different applications, is known to be NP-hard. This paper presents an O(|V|+|E|) algorithm to determine a lower bound for the Hamiltonian path completion number of a line graph. The algorithm is based on finding a collection of edge-disjoint trails dominating all the edges of the root graph G. The algorithm is tested by an extensive experimental study showing good performance suggesting its use as a building block of exact as well as heuristic solution approaches for the problem.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Applied Mathematics
Authors
Paolo Detti, Carlo Meloni, Marco Pranzo,