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.