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.
2012
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]
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11588/371206
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 20
  • ???jsp.display-item.citation.isi??? 15
social impact