Complexity analysis and optimization for the shortest path tour problem
(14 Sep 2010, 15:00)
Dipartimento di Informatica, Università di PIsa (Sala Seminari Est) - Relatore Paola Festa, Dipartimento di Matematica e Applicazioni "R. Caccioppoli", Università degli Studi di Napoli
:
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 and
sequentially pass through at least one node from given disjoint
node subsets. In this talk, it will proved that the SPTP belongs
to the complexity class P and several alternative techniques will
be presented to solve it. Furthermore, some variants of the SPTP will be discussed and proved to be special facility location
problems.