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