Vladimir Gurvich

Publications³⁹

• Chapter Gurvich V., Boros E., Elbassioni K. M., Makino K. A Potential Reduction Algorithm for Ergodic Two-Person Zero-Sum Limiting Average Payoff Stochastic Games, in: Combinatorial Optimization and Applications - 8th International Conference, COCOA 2014, Wailea, Maui, HI, USA, December 19-21, 2014, Proceedings. Springer, 2014. doi P. 694-709. doi
• Article Gurvich V., Gol'berg A., Andrade D. V., Borys K., Rudolf G. Combinatorial games modeling seki in GO // Discrete Mathematics. 2014. Vol. 329. P. 19-32. doi
• Article Gurvich V., Boros E., Milanic M. On CIS circulants // Discrete Mathematics. 2014. Vol. 318. P. 78-95. doi
• Article Gurvich V., Oudalov V. On Nash-solvability in pure stationary strategies of the deterministic n-person games with perfect information and mean or total effective cost // Discrete Applied Mathematics. 2014. Vol. 167. P. 131-143. doi
• Chapter Gurvich V., Boros E., Elbassioni K. M., Makino K. Markov Decision Processes and Stochastic Games with Total Effective Payoff, in: 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015), Leibniz International Proceedings in Informatics (LIPIcs) Vol. 30. Dagstuhl : Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2015. P. 103-115. doi
• Article Gurvich V., Boros E., Milanic M. On equistable, split, CIS, and related classes of graphs // Discrete Applied Mathematics. 2015 doi
• Article Gurvich V., Boros E. Sandwich problem for Π- and Δ-free multigraphs and its applications to positional games // Discrete Mathematics. 2015. Vol. 338. No. 12. P. 2421-2436. doi
• Article Gurvich V., Endre B., Khaled E., Kazuhisa M., Vladimir O. Sufficient conditions for the existence of Nash equilibria in bimatrix games in terms of forbidden $2 \times 2$ subgames // International Journal of Game Theory. 2016. Vol. 45. No. 4. P. 1111-1131. doi
• Article Boros E., Elbassioni K., Gurvich V., Makino K. A convex programming-based algorithm for mean payoff stochastic games with perfect information // Optimization Letters. 2017. Vol. 11. No. 8. P. 1499-1512. doi
• Article Boros E., Elbassioni K., Gurvich V., Makino K. A nested family of k-total effective rewards for positional games // International Journal of Game Theory. 2017. Vol. 46. No. 1. P. 263-293. doi
• Article Gurvich V., Boros E., Elbassioni K., Makino K. A Potential Reduction Algorithm for Two-Person Zero-Sum Mean Payoff Stochastic Games // Dynamic Games and Applications. 2018. Vol. 8. No. 1. P. 22-41. doi
• Article Gurvich V., Boros E., Milanič M., Oudalov V., Vičič J. A three-person deterministic graphical game without Nash equilibria // Discrete Applied Mathematics. 2018. Vol. 243. P. 21-38. doi
• Article Gurvich V., Boros E., Manthey B., Elbassioni K., Fouz M., Makino K. Approximation Schemes for Stochastic Mean Payoff Games with Perfect Information and Few Random Positions // Algorithmica. 2018. Vol. 80. No. 11. P. 3132-3157. doi
• Article Gurvich V. Backward induction in presence of cycles // Journal of Logic and Computation. 2018. Vol. 28. No. 7. P. 1635-1646. doi
• Chapter Gurvich V. Complexity of Generation, in: Computer Science – Theory and Applications 13th International Computer Science Symposium in Russia, CSR 2018, Moscow, Russia, June 6–10, 2018, Proceedings / Ed. by F. V. Fomin, V. V. Podolskii. Vol. 10846. Springer, 2018. doi P. 1-14. doi
• Article Gurvich V., Koshevoy G. Monotone bargaining is Nash-solvable // Discrete Applied Mathematics. 2018. P. 1-15. doi (in press)
• Chapter Gurvich V., Andrade D. V., Boros E. On graphs whose maximal cliques and stable sets intersect, in: Optimization Problems in Graph Theory Book 139. Springer, 2018. doi P. 3-63. doi
• Article Gurvich V., Nhan Bao H. On tame, pet, domestic, and miserable impartial games // Discrete Applied Mathematics. 2018. Vol. 243. P. 54-72. doi
• Article Gurvich V., Boros E., Kazuhisa M., Mursic P., Nhan Bao H. On the Sprague-Grundyfunction of Exact k- Nim // Discrete Applied Mathematics. 2018. Vol. 239. P. 1-14. doi
• Article Boros E., Elbassioni K. M., Gurvich V., Makino K. A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions // Information and Computation. 2019. Vol. 267. P. 74-95. doi
• Chapter Beisegel J., Chudnovsky M., Gurvich V., Milanič M., Servatius M. Avoidable Vertices and Edges in Graphs, in: Algorithms and Data Structures. WADS 2019. Lecture Notes in Computer Science Vol. 11646. Springer, 2019. P. 126-139. doi
• Article Boros E., Gurvich V., Milanic M. Decomposing 1-Sperner Hypergraphs // Electronic Journal of Combinatorics. 2019. Vol. 26. No. 3. P. 1-28. doi
• Article Boros E., Cepek O., Gurvich V. Separable discrete functions: Recognition and sufficient conditions // Discrete Mathematics. 2019. Vol. 342. No. 5. P. 1275-1292. doi
• Article Boros E., Gurvich V., Bao Ho N., Makino K., Mursic P. Sprague-Grundy function of matroids and related hypergraphs // Theoretical Computer Science. 2019. Vol. 799. P. 40-58. doi
• Article Boros E., Gurvich V., Bao Ho N., Makino K., Mursic P. Sprague–Grundy function of symmetric hypergraphs // Journal of Combinatorial Theory, Series A. 2019. Vol. 165. No. 7. P. 176-186. doi
• Article Boros E., Gurvich V., Milanic M. Characterizing and decomposing classes of threshold, split, and bipartite graphs via 1‐Sperner hypergraphs // Journal of Graph Theory. 2020. Vol. 94. No. 3. P. 364-397. doi
• Chapter Gurvich V., Vyalyi M. Computational hardness of multidimensional subtraction games, in: Computer Science – Theory and Applications 15th International Computer Science Symposium in Russia, CSR 2020, Yekaterinburg, Russia, June 29 – July 3, 2020, Proceedings Vol. 12159. Springer, 2020. doi P. 237-249. doi
• Article Boros E., Gurvich V., Bao Ho N., Makino K. On the Sprague–Grundy function of extensions of proper NIM // International Journal of Game Theory. 2020 doi
• Article Gurvich Vladimir, Naumova M. Logical Contradictions in the One-Way ANOVA and Tukey–Kramer Multiple Comparisons Tests with More Than Two Groups of Observations // Symmetry. 2021. Vol. 13. No. 8. Article 1387. doi
• Article Chikin N., Gurvich V., Knop K., Paterson M., Vyalyi M. More about Exact Slow k-Nim // Integers. Electronic Journal of Combinatorial Number Theory. 2021. Vol. 21. P. 1-14.
• Article Beisegel J., Chudnovsky M., Gurvich V., Martin M., Servatius M. Avoidable vertices and edges in graphs: Existence, characterization, and applications // Discrete Applied Mathematics. 2022. Vol. 309. P. 285-300. doi
• Article Gurvich V., Naumova M. Lexicographically maximal edges of dual hypergraphs and Nash-solvability of tight game forms // Annals of Mathematics and Artificial Intelligence. 2022 doi
• Article Gurvich V., Krnc M., Milanič M., Vyalyi M. Shifting paths to avoidable ones // Journal of Graph Theory. 2022. Vol. 100. No. 1. P. 69-83. doi
• Article Gurvich V., Naumova M. Computing lexicographically safe Nash equilibria in finite two-person games with tight game forms given by oracles // Discrete Applied Mathematics. 2023. Vol. 340. P. 53-68. doi
• Article Boros E., Franciosa P. G., Gurvich V., Vyalyi M. Deterministic n-person shortest path and terminal games on symmetric digraphs have Nash equilibria in pure stationary strategies // International Journal of Game Theory. 2023. P. 1-25. doi
• Preprint Gurvich V., Parfenov A., Vyalyi M. Experimental Study of the Game Exact Nim(5, 2) / Cornell University. Series arXiv "math". 2023. doi
• Article Boros E., Gurvich V., Bao Ho N., Makino K., Mursic P. Impartial games with decreasing Sprague–Grundy function and their hypergraph compound // International Journal of Game Theory. 2023 doi
• Article Boros E., Gurvich V., Kitrossky L., Makino K. On the Sprague-Grundy Function of Compound Games // Integers. Electronic Journal of Combinatorial Number Theory. 2023. No. 23. P. 1-20. doi
• Article Boros E., Cepek O., Gurvich V., Makino K. Recognizing distributed approval voting forms and correspondences // Annals of Operations Research. 2023 doi