Name
Abstract | ||
|---|---|---|
We consider shortest path problems defined on graphs with random are costs. We assume that information on are cost values is accumulated as the graph is being traversed. The objective is to devise a policy that leads from an origin to a destination node with minimal expected cost. We provide dynamic programming algorithms, estimates for their complexity, negative complexity results, and analysis of some possible heuristic algorithms. (C) 1996 John Wiley & Sons, Inc. |
Year | DOI | Venue |
|---|---|---|
1996 | 10.1002/(SICI)1097-0037(199603)27:2<133::AID-NET5>3.0.CO;2-L | NETWORKS |
Keywords | Field | DocType |
algorithm,dynamic programming,shortest path,shortest path problem,dynamic programming algorithm,random graph,heuristic algorithm,graph theory,computational complexity | Graph theory,Dynamic programming,Combinatorics,Heuristic,Mathematical optimization,Random graph,Shortest path problem,Algorithm,Constrained Shortest Path First,Mathematics,Computational complexity theory,K shortest path routing | Journal |
Volume | Issue | ISSN |
27 | 2 | 0028-3045 |
Citations | PageRank | References |
74 | 4.98 | 10 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| george polychronopoulos | 1 | 74 | 4.98 |
| John N. Tsitsiklis | 2 | 5300 | 621.34 |
| decision systems | 3 | 159 | 34.45 |