Day - Time: 2010-09-14 15:00
Place: 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.