Name
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. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1016/j.amc.2013.06.020 | Applied Mathematics and Computation |
Keywords | Field | DocType |
extensive experimental study,root graph g.,different application,building block,line graph l,graph g,hamiltonian path completion number,minimum number,hamiltonian path,line graph,line graphs,lower bound | Strength of a graph,Discrete mathematics,Mathematical optimization,Combinatorics,Line graph,Graph power,Hamiltonian path,Quartic graph,Hamiltonian path problem,Mathematics,Complement graph,Path graph | Journal |
Volume | ISSN | Citations |
220 | 0096-3003 | 0 |
PageRank | References | Authors |
0.34 | 19 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Paolo Detti | 1 | 144 | 19.55 |
| Carlo Meloni | 2 | 71 | 9.79 |
| Marco Pranzo | 3 | 307 | 22.56 |