A constructive algorithm for max-min paths problems on energy networks

摘要

Max-min paths problems on energy networks are the main center of interest of this article. They typically arose as an auxiliary problem within the study of a special class of discrete min-max control models and within so-called cyclic games. These two classes generalize the well-known combinatorial problem of the shortest and the longest paths in a weighted directed graph. A constructive algorithm for determining the tree of max-min paths in these special networks is proposed. Furthermore, we apply it as a new approach to the solution of special zero value cyclic games. Such a class is not too restrictive. Furthermore we refer to more general models which are very close to real-world examples. (C) 2008 Elsevier Inc. All rights reserved.