Name
Abstract | ||
|---|---|---|
Given a graph G with a label (color) assigned to each edge (not necessarily properly) we look for an hamiltonian cycle of G with the minimum number of different colors. The problem has several applications in telecommunication networks, electric networks, multimodal transportation networks, among others, where one aims to ensure connectivity or other properties by means of limited number of different connections. We analyze the complexity of the problem on special graph classes and propose, for the general case, heuristic resolution algorithms. Performances of the algorithms are experimentally evaluated on a set of instances and compared with the exact solution value provided by a solver. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1016/j.endm.2006.06.080 | Electronic Notes in Discrete Mathematics |
Keywords | Field | DocType |
Labelled graph algorithms,Hamiltonian cycles,Tabu search | Discrete mathematics,Combinatorics,Mathematical optimization,Heuristic,Graph power,Hamiltonian path,Hamiltonian path problem,Graph bandwidth,Factor-critical graph,Solver,Mathematics,Voltage graph | Journal |
Volume | ISSN | Citations |
25 | 1571-0653 | 7 |
PageRank | References | Authors |
0.54 | 3 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| R. Cerulli | 1 | 252 | 23.85 |
| P. Dell'Olmo | 2 | 151 | 15.33 |
| M. Gentili | 3 | 32 | 3.35 |
| A. Raiconi | 4 | 131 | 9.68 |