18 citations · 42 across the 38 of their papers we have counts for
Showing 2008Show all
2 papers · 1 filter
cs.GT2008★ 3 cited
On the computational complexity of solving stochastic mean-payoff games
Vladimir Gurvich, Peter Bro Miltersen
We consider some well-known families of two-player, zero-sum, perfect information games that can be viewed as special cases of Shapley's stochastic games. We show that the followin…
cs.CC2008
Characterization of the Vertices and Extreme Directions of the Negative Cycles Polyhedron and Hardness of Generating Vertices of 0/1-Polyhedra
Endre Boros, Khaled Elbassioni, Vladimir Gurvich +1
Given a graph and a weight function on the edges $w:E\mapsto\RR$, we consider the polyhedron of negative-weight flows on , and get a complete characterization…