Name
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 node subsets T 1, T 2, . . . , T N , where \({T_i \cap T_j = \emptyset, \forall\ i, j=1,\ldots,N,\ i \neq j}\). 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. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/s11590-010-0258-y | Optimization Letters |
Keywords | Field | DocType |
Shortest path problems, Network flow problems, Network optimization, Combinatorial optimization | Complexity class,Discrete mathematics,Mathematical optimization,Combinatorics,Shortest path problem,Constrained Shortest Path First,Directed graph,Arc length,Combinatorial optimization,Mathematics,K shortest path routing | Journal |
Volume | Issue | ISSN |
6 | 1 | 1862-4480 |
Citations | PageRank | References |
8 | 0.66 | 9 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Paola Festa | 1 | 287 | 25.32 |