The shortest path tour problem consists of finding a shortest path from a given origin node s to a given destination node d in a graph with nonnegative arc lengths with the constraint that the path should successively pass through at least one node from given node subsets T1 ,T2 ,...,Tk [i.e., start at s, move to some node in T1 (possibly through some intermediate nodes that are not in T1), then move to some node in T2 (possibly through some intermediate nodes that are not in T2, but may be in T1 ),etc., move to some node in Tk ,and then to d (possibly through some intermediate nodes not equal to d)]. In this talk, the complexity class will be demostrated to which the problem belongs and several alternative techniques will be presented to exactly solve it.
Complexity analysis and optimization for the shortest path tour problem / Festa, Paola. - (2010).
Complexity analysis and optimization for the shortest path tour problem
FESTA, PAOLA
2010
Abstract
The shortest path tour problem consists of finding a shortest path from a given origin node s to a given destination node d in a graph with nonnegative arc lengths with the constraint that the path should successively pass through at least one node from given node subsets T1 ,T2 ,...,Tk [i.e., start at s, move to some node in T1 (possibly through some intermediate nodes that are not in T1), then move to some node in T2 (possibly through some intermediate nodes that are not in T2, but may be in T1 ),etc., move to some node in Tk ,and then to d (possibly through some intermediate nodes not equal to d)]. In this talk, the complexity class will be demostrated to which the problem belongs and several alternative techniques will be presented to exactly solve it.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
