The shortest path tour problem (SPTP) consists in finding a shortest path from a given origination node s to a given destination node d in a directed graph with nonnegative arc lengths with the constraint that the optimal path P should successively and sequentially pass through at least one node from given disjoint node subsets T1, T2, . . . , TN. In this paper, it will proved that the SPTP belongs to the complexity class P and several alternative techniques will be presented to solve it.
Complexity analysis and optimization of the shortest path tour problem / Festa, Paola. - In: OPTIMIZATION LETTERS. - ISSN 1862-4472. - 6:1(2012), pp. 163-175. [10.1007/s11590-010-0258-y]
Complexity analysis and optimization of the shortest path tour problem
FESTA, PAOLA
2012
Abstract
The shortest path tour problem (SPTP) consists in finding a shortest path from a given origination node s to a given destination node d in a directed graph with nonnegative arc lengths with the constraint that the optimal path P should successively and sequentially pass through at least one node from given disjoint node subsets T1, T2, . . . , TN. In this paper, it will proved that the SPTP belongs to the complexity class P and several alternative techniques will be presented to solve it.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.