Vladimir Gurvich

Ann. Math. Artif. Intell., January, 2024

Growing Trees and Amoebas' Replications.

[BibT_eX]

[DOI]

Matjaz Krnc

Mikhail N. Vyalyi

CoRR, 2024

2023

Computing lexicographically safe Nash equilibria in finite two-person games with tight game forms given by oracles.

[BibT_eX]

[DOI]

Discret. Appl. Math., December, 2023

Experimental Study of the Game Exact Nim(5, 2).

[BibT_eX]

[DOI]

Artem Parfenov

Michael N. Vyalyi

CoRR, 2023

Computing Remoteness Functions of Moore, Wythoff, and Euclid's games.

[BibT_eX]

[DOI]

CoRR, 2023

Dually conformal hypergraphs.

[BibT_eX]

[DOI]

CoRR, 2023

2022

Shifting paths to avoidable ones.

[BibT_eX]

[DOI]

J. Graph Theory, 2022

Metric and ultrametric inequalities for directed graphs.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2022

Avoidable vertices and edges in graphs: Existence, characterization, and applications.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2022

Avoidability beyond paths.

[BibT_eX]

[DOI]

CoRR, 2022

On Nash-Solvability of Finite Two-Person Tight Vector Game Forms.

[BibT_eX]

[DOI]

CoRR, 2022

Deterministic n-person shortest path and terminal games on symmetric digraphs have Nash equilibria in pure stationary strategies.

[BibT_eX]

[DOI]

Paolo Giulio Franciosa

Michael N. Vyalyi

CoRR, 2022

2021

Logical Contradictions in the One-Way ANOVA and Tukey-Kramer Multiple Comparisons Tests with More Than Two Groups of Observations.

[BibT_eX]

[DOI]

Symmetry, 2021

On the Sprague-Grundy function of extensions of proper Nim.

[BibT_eX]

[DOI]

Int. J. Game Theory, 2021

Balanced flows for transshipment problems.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2021

On Nash-solvability of finite n-person shortest path games; bi-shortest path conjecture.

[BibT_eX]

[DOI]

CoRR, 2021

On Nash-solvability of finite n-person deterministic graphical games; Catch 22.

[BibT_eX]

[DOI]

CoRR, 2021

Polynomial algorithms computing two lexicographically safe Nash equilibria in finite two-person games with tight game forms given by oracles.

[BibT_eX]

[DOI]

CoRR, 2021

On Nash-solvability of n-person graphical games under Markov's and a priori realizations.

[BibT_eX]

[DOI]

CoRR, 2021

On Computational Hardness of Multidimensional Subtraction Games.

[BibT_eX]

[DOI]

Mikhail N. Vyalyi

Algorithms, 2021

2020

Characterizing and decomposing classes of threshold, split, and bipartite graphs via 1-Sperner hypergraphs.

[BibT_eX]

[DOI]

J. Graph Theory, 2020

On the degree sequences of dual graphs on surfaces.

[BibT_eX]

[DOI]

CoRR, 2020

2019

Sprague-Grundy function of matroids and related hypergraphs.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2019

Sprague-Grundy function of symmetric hypergraphs.

[BibT_eX]

[DOI]

J. Comb. Theory, Ser. A, 2019

A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions.

[BibT_eX]

[DOI]

Inf. Comput., 2019

Separable discrete functions: Recognition and sufficient conditions.

[BibT_eX]

[DOI]

Ondrej Cepek

Discret. Math., 2019

Decomposing 1-Sperner Hypergraphs.

[BibT_eX]

[DOI]

Electron. J. Comb., 2019

Avoidable Vertices and Edges in Graphs.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures - 16th International Symposium, 2019

2018

Backward induction in presence of cycles.

[BibT_eX]

[DOI]

J. Log. Comput., 2018

A Potential Reduction Algorithm for Two-Person Zero-Sum Mean Payoff Stochastic Games.

[BibT_eX]

[DOI]

Dyn. Games Appl., 2018

Monotone bargaining is Nash-solvable.

[BibT_eX]

[DOI]

Gleb A. Koshevoy

Discret. Appl. Math., 2018

On tame, pet, domestic, and miserable impartial games.

[BibT_eX]

[DOI]

Nhan Bao Ho

Discret. Appl. Math., 2018

A three-person deterministic graphical game without Nash equilibria.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2018

On the Sprague-Grundyfunction of Exact k-Nim.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2018

Approximation Schemes for Stochastic Mean Payoff Games with Perfect Information and Few Random Positions.

[BibT_eX]

[DOI]

Algorithmica, 2018

Complexity of Generation.

[BibT_eX]

[DOI]

Proceedings of the Computer Science - Theory and Applications, 2018

2017

A convex programming-based algorithm for mean payoff stochastic games with perfect information.

[BibT_eX]

[DOI]

Optim. Lett., 2017

A nested family of $\varvec{k}$ -total effective rewards for positional games.

[BibT_eX]

[DOI]

Int. J. Game Theory, 2017

On equistable, split, CIS, and related classes of graphs.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2017

2016

Sufficient conditions for the existence of Nash equilibria in bimatrix games in terms of forbidden $2 \times 2$ subgames.

[BibT_eX]

[DOI]

Int. J. Game Theory, 2016

A three-person chess-like game without Nash equilibria.

[BibT_eX]

[DOI]

CoRR, 2016

2015

Sandwich problem for Π- and Δ-free multigraphs and its applications to positional games.

[BibT_eX]

[DOI]

Discret. Math., 2015

1-Sperner hypergraphs.

[BibT_eX]

[DOI]

CoRR, 2015

Markov Decision Processes and Stochastic Games with Total Effective Payoff.

[BibT_eX]

[DOI]

Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science, 2015

2014

Combinatorial games modeling seki in GO.

[BibT_eX]

[DOI]

Discret. Math., 2014

On CIS circulants.

[BibT_eX]

[DOI]

Discret. Math., 2014

On Nash-solvability in pure stationary strategies of the deterministic n-person games with perfect information and mean or total effective cost.

[BibT_eX]

[DOI]

Vladimir Oudalov

Discret. Appl. Math., 2014

A four-person chess-like game without Nash equilibria in pure stationary strategies.

[BibT_eX]

[DOI]

Vladimir Oudalov

CoRR, 2014

Nested Family of Cyclic Games with $k$-total Effective Rewards.

[BibT_eX]

[DOI]

CoRR, 2014

A Potential Reduction Algorithm for Ergodic Two-Person Zero-Sum Limiting Average Payoff Stochastic Games.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Optimization and Applications, 2014

2013

On discounted approximations of undiscounted stochastic games and Markov decision processes with limited randomness.

[BibT_eX]

[DOI]

Oper. Res. Lett., 2013

A polynomial algorithm for a two parameter extension of Wythoff NIM based on the Perron-Frobenius theory.

[BibT_eX]

[DOI]

Vladimir Oudalov

Int. J. Game Theory, 2013

On Canonical Forms for Zero-Sum Stochastic Mean Payoff Games.

[BibT_eX]

[DOI]

Dyn. Games Appl., 2013

2012

On Nash equilibria and improvement cycles in pure positional strategies for Chess-like and Backgammon-like n-person games.

[BibT_eX]

[DOI]

Discret. Math., 2012

Total tightness implies Nash-solvability for three-person game forms.

[BibT_eX]

[DOI]

Ondrej Cepek

Discret. Math., 2012

Characterizing (quasi-)ultrametric finite spaces in terms of (directed) graphs.

[BibT_eX]

[DOI]

Mikhail N. Vyalyi

Discret. Appl. Math., 2012

Further generalizations of the Wythoff game and the minimum excludant.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2012

2011

On exact blockers and anti-blockers, Δ-conjecture, and related problems.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2011

Nash-solvable two-person symmetric cycle game forms.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2011

The negative cycles polyhedron and hardness of checking some polyhedral properties.

[BibT_eX]

[DOI]

Ann. Oper. Res., 2011

Stochastic Mean Payoff Games: Smoothed Analysis and Approximation Schemes.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

2010

On effectivity functions of game forms.

[BibT_eX]

[DOI]

Games Econ. Behav., 2010

Friendship Two-Graphs.

[BibT_eX]

[DOI]

Graphs Comb., 2010

Scarf Oiks.

[BibT_eX]

[DOI]

Jack Edmonds

Stéphane Gaubert

Electron. Notes Discret. Math., 2010

Sperner Oiks.

[BibT_eX]

[DOI]

Jack Edmonds

Stéphane Gaubert

Electron. Notes Discret. Math., 2010

Acyclic, or totally tight, two-person game forms: Characterization and main properties.

[BibT_eX]

[DOI]

Discret. Math., 2010

Not complementary connected and not CIS d-graphs form weakly monotone families.

[BibT_eX]

[DOI]

Diogo Vieira Andrade

Discret. Math., 2010

Metric and ultrametric spaces of resistances.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2010

On acyclicity of games with cycles.

[BibT_eX]

[DOI]

Daniel Andersson

Thomas Dueholm Hansen

Discret. Appl. Math., 2010

A Pumping Algorithm for Ergodic Stochastic Mean Payoff Games with Perfect Information.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2010

2009

Minimal and locally minimal games and game forms.

[BibT_eX]

[DOI]

Kazuhisa Makino

Discret. Math., 2009

Vertex- and edge-minimal and locally minimal graphs.

[BibT_eX]

[DOI]

Discret. Math., 2009

Neighborhood hypergraphs of digraphs and some matrix permutation problems.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2009

Decomposing complete edge-chromatic graphs and hypergraphs. Revisited.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2009

On split and almost CIS-graphs.

[BibT_eX]

[DOI]

Australas. J Comb., 2009

2008

On Short Paths Interdiction Problems: Total and Node-Wise Limited Interdiction.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2008

Neighborhood hypergraphs of bipartite graphs.

[BibT_eX]

[DOI]

J. Graph Theory, 2008

War and peace in veto voting.

[BibT_eX]

[DOI]

Eur. J. Oper. Res., 2008

On cyclically orientable graphs.

[BibT_eX]

[DOI]

Discret. Math., 2008

Generating 3-vertex connected spanning subgraphs.

[BibT_eX]

[DOI]

Discret. Math., 2008

Generating All Vertices of a Polyhedron Is Hard.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 2008

Generating all minimal integral solutions to AND-OR systems of monotone inequalities: Conjunctions are simpler than disjunctions.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2008

Recalling Leo.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2008

Scientific contributions of Leo Khachiyan (a short overview).

[BibT_eX]

[DOI]

Discret. Appl. Math., 2008

On the computational complexity of solving stochastic mean-payoff games

[BibT_eX]

[DOI]

Peter Bro Miltersen

CoRR, 2008

Characterization of the vertices and extreme directions of the negative cycle polyhedron and harness of generating vertices of $0/1$-polyhedra

[BibT_eX]

[DOI]

CoRR, 2008

On Enumerating Minimal Dicuts and Strongly Connected Subgraphs.

[BibT_eX]

[DOI]

Algorithmica, 2008

Generating Cut Conjunctions in Graphs and Related Problems.

[BibT_eX]

[DOI]

Algorithmica, 2008

A Complete Characterization of Nash-Solvability of Bimatrix Games in Terms of the Exclusion of Certain 2×2 Subgames.

[BibT_eX]

[DOI]

Proceedings of the Computer Science, 2008

2007

Dual-bounded generating problems: Efficient and inefficient points for discrete probability distributions and sparse boxes for multidimensional data.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2007

On the dualization of hypergraphs with bounded edge-intersections and other related classes of hypergraphs.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2007

Computing Many Maximal Independent Sets for Hypergraphs in Parallel.

[BibT_eX]

[DOI]

Parallel Process. Lett., 2007

A global parallel algorithm for the hypergraph transversal problem.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2007

On the misere version of game Euclid and miserable games.

[BibT_eX]

[DOI]

Discret. Math., 2007

Enumerating disjunctions and conjunctions of paths and cuts in reliability theory.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2007

Generating Minimal k-Vertex Connected Spanning Subgraphs.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics, 13th Annual International Conference, 2007

2006

Transversal hypergraphs to perfect matchings in bipartite graphs: Characterization and generation algorithms.

[BibT_eX]

[DOI]

Khaled M. Elbassioni

J. Graph Theory, 2006

Perfect graphs, kernels, and cores of cooperative games.

[BibT_eX]

[DOI]

Discret. Math., 2006

An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2006

Enumerating Spanning and Connected Subsets in Graphs and Matroids.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2006

Extending Dijkstra's Algorithm to Maximize the Shortest Path by Node-Wise Limited Arc Interdiction.

[BibT_eX]

[DOI]

Leonid Khachiyan

Jihui Zhao

Proceedings of the Computer Science, 2006

2005

On the Complexity of Some Enumeration Problems for Matroids.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2005

Comparison of Convex Hulls and Box Hulls.

[BibT_eX]

Ying Liu

Ars Comb., 2005

Generating All Minimal Integral Solutions to Monotone and, or-Systems of Linear, Transversal and Polymatroid Inequalities.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2005, 2005

Generating Cut Conjunctions and Bridge Avoiding Extensions in Graphs.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, 16th International Symposium, 2005

A New Algorithm for the Hypergraph Transversal Problem.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics, 11th Annual International Conference, 2005

2004

Difference graphs.

[BibT_eX]

[DOI]

Roy Meshulam

Discret. Math., 2004

Stable matchings in three-sided systems with cyclic preferences.

[BibT_eX]

[DOI]

Discret. Math., 2004

Dual-bounded generating problems: weighted transversals of a hypergraph.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2004

An Efficient Implementation of a Joint Generation Algorithm.

[BibT_eX]

[DOI]

Proceedings of the Experimental and Efficient Algorithms, Third International Workshop, 2004

Generating Paths and Cuts in Multi-pole (Di)graphs.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2004, 2004

Generating Maximal Independent Sets for Hypergraphs with Bounded Edge-Intersections.

[BibT_eX]

[DOI]

Proceedings of the LATIN 2004: Theoretical Informatics, 2004

Enumerating Minimal Dicuts and Strongly Connected Subgraphs and Related Geometric Problems.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2004

Algorithms for Generating Minimal Blockers of Perfect Matchings in Bipartite Graphs and Related Problems.

[BibT_eX]

[DOI]

Khaled M. Elbassioni

Proceedings of the Algorithms, 2004

A stronger version of Bárány's theorem in the plane.

[BibT_eX]

[DOI]

Khaled M. Elbassioni

Amr Elmasry

Proceedings of the 16th Canadian Conference on Computational Geometry, 2004

2003

On Nash-solvability in pure stationary strategies of finite games with perfect information which may have cycles.

[BibT_eX]

[DOI]

Math. Soc. Sci., 2003

Extending the Balas-Yu bounds on the number of maximal independent sets in graphs to hypergraphs and lattices.

[BibT_eX]

[DOI]

Math. Program., 2003

An inequality for polymatroid functions and its applications.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2003

On Maximal Frequent and Minimal Infrequent Sets in Binary Matrices.

[BibT_eX]

[DOI]

Ann. Math. Artif. Intell., 2003

Algorithms for Enumerating Circuits in Matroids.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, 14th International Symposium, 2003

An Intersection Inequality for Discrete Distributions and Related Generation Problems.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 30th International Colloquium, 2003

An Efficient Implementation of a Quasi-polynomial Algorithm for Generating Hypergraph Transversals.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2003

2002

Dual-Bounded Generating Problems: All Minimal Integer Solutions for a Monotone System of Linear Inequalities.

[BibT_eX]

[DOI]

SIAM J. Comput., 2002

Generating dual-bounded hypergraphs.

[BibT_eX]

[DOI]

Optim. Methods Softw., 2002

Recursive generation of partitionable graphs.

[BibT_eX]

[DOI]

Stefan Hougardy

J. Graph Theory, 2002

Camel sequences and quadratic residues.

[BibT_eX]

[DOI]

Vladimir A. Gurvich

Li Sheng

Discret. Appl. Math., 2002

On the Complexity of Generating Maximal Frequent and Minimal Infrequent Sets.

[BibT_eX]

[DOI]

Proceedings of the STACS 2002, 19th Annual Symposium on Theoretical Aspects of Computer Science, Antibes, 2002

Matroid Intersections, Polymatroid Inequalities, and Related Problems.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2002, 2002

2001

On Generating All Minimal Integer Solutions for a Monotone System of Linear Inequalities.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 28th International Colloquium, 2001

2000

Dual-Bounded Generating Problems: Partial and Multiple Transversals of a Hypergraph.

[BibT_eX]

[DOI]

SIAM J. Comput., 2000

An Efficient Incremental Algorithm for Generating All Maximal Independent Sets in Hypergraphs of Bounded Dimension.

[BibT_eX]

[DOI]

Parallel Process. Lett., 2000

Stable effectivity functions and perfect graphs.

[BibT_eX]

[DOI]

Math. Soc. Sci., 2000

Generating Partial and Multiple Transversals of a Hypergraph.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000

1999

On Generating the Irredundant Conjunctive and Disjunctive Normal Forms of Monotone Boolean Functions.

[BibT_eX]

[DOI]

Leonid Khachiyan

Discret. Appl. Math., 1999

1998

On minimal imperfect graphs with circular symmetry.

[BibT_eX]

[DOI]

J. Graph Theory, 1998

A corrected version of the Duchet kernel conjecture.

[BibT_eX]

[DOI]

Discret. Math., 1998

A circular graph - counterexample to the Duchet kernel conjecture.

[BibT_eX]

[DOI]

A. Apartsin

E. Ferapontova

Discret. Math., 1998

1997

On the frequency of the most frequently occurring variable in dual monotone DNFs.

[BibT_eX]

[DOI]

Leonid Khachiyan

Discret. Math., 1997

1996

Perfect graphs are kernel solvable.

[BibT_eX]

[DOI]

Discret. Math., 1996

1995

Trees as semilattices.

[BibT_eX]

[DOI]

Leonid Libkin