The shortest path tour problem (SPTP) consists of finding a shortest path from a given origin 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 pass through at least one node from given 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 exactly solve it.
The shortest path tour problem: problem definition, modeling, and optimization / Festa, Paola. - (2009), pp. 1-7. ( International Network Optimization Conference - INOC 2009 Pisa, Italia 26-28 aprile 2009).
The shortest path tour problem: problem definition, modeling, and optimization
FESTA, PAOLA
2009
Abstract
The shortest path tour problem (SPTP) consists of finding a shortest path from a given origin 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 pass through at least one node from given 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 exactly solve it.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
