**Authors:** Lozovanu Dmitrii
**Keywords:** Max-min path, positional games, c-game on networks.

### Abstract

We study the max-min paths problem, which represents a game version of the shortest and the longest paths problem in a weighted directed graph. In this problem the vertex set V of the weighted directed graph G=(V,E) is divided into two disjoint subsets V

_{A} and V

_{B} which are regarded as positional sets of two players. The players are seeking for a directed path from the given starting position ν

_{0} to the final position ν

_{f} , where the first player intends to maximize the integral cost of the path while the second one has aim to minimize it. Polynomial-time algorithm for determining max-min path in networks is proposed and its application for solving zero value cyclic games is developed. Mathematics Subject Classification 2000: 90B10, 90C35, 90C27.

D.D. Lozovanu

Institute of Mathematics and Computer Science,

5 Academiei str.

Chisinau, MD-2028, Moldova.

E-mail:

### Fulltext

–

0.19 Mb