Name
Abstract | ||
|---|---|---|
Given an undirected weighted graph, in which each vertex is assigned to a color and one of them is identified as source, in the all-colors shortest path problem we look for a minimum cost shortest path that starts from the source and spans all different colors. The problem is known to be NP-Hard and hard to approximate. In this work we propose a variant of the problem in which the source is unspecified and show the two problems to be computationally equivalent. Furthermore, we propose a mathematical formulation, a compact representation for feasible solutions and a VNS metaheuristic that is based on it. Computational results show the effectiveness of the proposed approach for the two problems. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1007/s10589-018-0014-2 | Comp. Opt. and Appl. |
Keywords | Field | DocType |
Shortest path, Colored graph, Variable neighboord search | Graph,Mathematical optimization,Vertex (geometry),Variable neighborhood search,Shortest path problem,Mathematics,Metaheuristic | Journal |
Volume | Issue | ISSN |
71 | 2 | 0926-6003 |
Citations | PageRank | References |
0 | 0.34 | 17 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Francesco Carrabs | 1 | 199 | 15.55 |
| R. Cerulli | 2 | 252 | 23.85 |
| R. Pentangelo | 3 | 0 | 0.34 |
| A. Raiconi | 4 | 131 | 9.68 |