zbMATH — the first resource for mathematics

On the minimax path in a network. (English. Russian original) Zbl 0821.90127
Discrete Math. Appl. 4, No. 5, 447-453 (1994); translation from Diskretn. Mat. 6, No. 2, 138-144 (1994).
Summary: A minimax problem for a network is described. The problem generalizes the shortest and the longest path problems for networks and has applications in the theory of acyclic games. An algorithm is given that solves the problem using \(O(n^ 3)\) elementary operations, where \(n\) is the number of nodes in the network.

90C35 Programming involving graphs or networks
90C60 Abstract computational complexity for mathematical programming problems
91A20 Multistage and repeated games
PDF BibTeX Cite
Full Text: DOI