Research and Advances

Optimal paths in graphs with stochastic or multidimensional weights

This paper explores computationally tractable formulations of stochastic and multidimensional optimal path problems, each as an extension of the shortest path problem. A single formulation encompassing both problems is considered, in which a utility function defines preference among candidate paths. The result is the ability to state explicit conditions for exact solutions using standard methods, and the applicability of well-understood approximation techniques.

Advertisement

Author Archives

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved