IMI/Publicaţii/CSJM/Ediţii/CSJM v.13, n.2 (38), 2005/

Polynomial Time Algorithm for Determining Max-Min Paths in Networks and Solving Zero Value Cyclic Games

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


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 VA and VB 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.


Adobe PDF document0.19 Mb