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.
Heuristic Aproaches for the Minimum Labelling Hamiltonian Cycle Problem / Cerulli, R; Dell'Olmo, Paolo; Gentili, M; Raiconi, Andrea. - In: ELECTRONIC NOTES IN DISCRETE MATHEMATICS. - ISSN 1571-0653. - ELETTRONICO. - 25:(2006), pp. 131-138. [10.1016/j.endm.2006.06.080]
Heuristic Aproaches for the Minimum Labelling Hamiltonian Cycle Problem
DELL'OLMO, Paolo;RAICONI, ANDREA
2006
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.