18 citations · 42 across the 38 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
cs.CC2020
Computational Hardness of Multidimensional Subtraction Games
Vladimir Gurvich, Michael Vyalyi
We study algorithmic complexity of solving subtraction games in a~fixed dimension with a finite difference set. We prove that there exists a game in this class such that any algori…
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…