• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site
Of all publications in the section: 28
Sort:
by name
by year
Article
Malyshev D. Discrete Applied Mathematics. 2016. Vol. 203. P. 117-126.

We completely determine the complexity status of the dominating set problem for hereditary graph classes defined by forbidden induced subgraphs with at most five vertices.

Added: Oct 9, 2015
Article
Веселов С. И., Gribanov D., Zolotykh N. et al. Discrete Applied Mathematics. 2019.

In Chirkov et al., (2019), classes of conic and discrete conic functions were introduced. In this paper we use the term convic instead conic. The class of convic functions properly includes the classes of convex functions, strictly quasiconvex functions and the class of quasiconvex polynomials. On the other hand, the class of convic functions is properly included in the class of quasiconvex functions. The discrete convic function is a discrete analogue of the convic function. In Chirkov et al., (2019), the lower bound 3^{n-1} log(R) for the number of calls to the comparison oracle needed to find the minimum of the discrete convic function defined on integer points of some n-dimensional ball with radius R was obtained. But the problem of the existence of a polynomial (in log(R) for fixed n) algorithm for minimizing such functions has remained open. In this paper, we answer positively the question of the existence of such an algorithm. Namely, we propose an algorithm for minimizing discrete convic functions that uses 2^{n^2 log(n)} log(R) calls to the comparison oracle and has  2^{n^2 log(n)} poly(log(R)) bit complexity.

Added: Oct 29, 2019
Article
Dietzenbacher B., Borm P., Hendrickx R. Discrete Applied Mathematics. 2019. P. 1-25.

This paper introduces and analyzes a procedural egalitarian solution for nontransferable utility games. This concept is based on an egalitarian procedure in which egalitarian opportunities of coalitions are explicitly taken into account. We formulate conditions under which the new solution prescribes a core element and derive a direct expression on the class of bargaining games and the class of bankruptcy games.

Added: Dec 10, 2019
Article
Gurvich V., Boros E., Milanič M. et al. Discrete Applied Mathematics. 2018. Vol. 243. P. 21-38.

We give an example of a three-person deterministic graphical game that has no Nash equilibrium in pure stationary strategies. The game has seven positions, four outcomes (a unique cycle and three terminal positions), and its normal form is of size 2×2×4 only. Thus, the example strengthens significantly the one obtained in 2014 by Gurvich and Oudalov; the latter has four players, five terminals, and normal form of size 2×4×6×8. Furthermore, our example is minimal with respect to the number of players. Somewhat similar examples were known since 1975, but they were not related to deterministic graphical games. The small size of our example allows us to verify that it has no Nash equilibrium not only in pure but also in independently mixed (so-called behavioral) strategies. For independently mixed strategies two distinct effective payoffs can be considered: along with the classical Markovian evaluation, we also consider a priori evaluation, which may be a better fit for playing in behavioral strategies. We show that in both cases Nash equilibria may fail to exist.

Added: Oct 10, 2018
Article
Gurvich V., Vyalyi M. Discrete Applied Mathematics. 2012. Vol. 160. P. 1742-1756.
Added: Oct 18, 2014
Article
Kuznetsov S., Babin M. A. Discrete Applied Mathematics. 2013. Vol. 161. No. 6. P. 742-749.

The problem of recognizing whether a subset of attributes is a premise of a minimal cover of functional dependencies of a relation is shown to be coNP-complete. The complexity of some related decision, enumerating, and sampling problems on functional dependencies, FCA implications, and closed sets of attributes is discussed.

Added: Jun 2, 2013
Article
Akhmejanova M., Shabanov D. A. Discrete Applied Mathematics. 2020. Vol. 276. P. 2-12.

The paper deals with an extremal problem concerning equitable colorings of uniform hypergraphs. Recall that a vertex coloring of a hypergraph is called proper if there are no monochromatic edges under this coloring. A hypergraph is said to be equitably r-colorable if there is a proper coloring with r colors such that the sizes of any two color classes differ by at most one. In the present paper we prove a new lower for the number of edges for an n-uniform hypergraph taht does not admit an equitable r-coloring.

Added: Oct 31, 2019
Article
Shabanov D. A. Discrete Applied Mathematics. 2020. Vol. 282. P. 168-183.

The paper deals with estimating the r-colorability threshold for a random k-uniform hypergraph in the binomial model H(n,k,p). We consider the sparse case, when the expected number of edges is a linear function of n and prove a new lower bound for the sharp threshold of the property that  H(n,k,p) is r-colorable.

Added: Jun 6, 2020
Article
Alam M., Buzmakov A. V., Napoli A. Discrete Applied Mathematics. 2018. Vol. 249. P. 2-17.

With an increased interest in machine processable data and with the progress of semantic technologies, many datasets are now published in the form of RDF triples for constituting the so-called Web of Data. Data can be queried using SPARQL but there are still needs for integrating, classifying and exploring the data for data analysis and knowledge discovery purposes. This research work proposes a new approach based on Formal Concept Analysis and Pattern Structures for building a pattern concept lattice from a set of RDF triples. This lattice can be used for data exploration and in particular visualized thanks to an adapted tool. The specific pattern structure introduced for RDF data allows to make a bridge with other studies on the use of structured attribute sets when building concept lattices. Our approach is experimentally validated on the classification of RDF data showing the efficiency of the underlying algorithms.

Added: Sep 26, 2017
Article
Beaudou L., Foucaud F., Naserasr R. Discrete Applied Mathematics. 2019. Vol. 261. P. 40-51.

A signed graph is a graph and a subset of its edges which corresponds to an assignment of signs to the edges: edges in are negative while edges not in are positive. A closed walk of a signed graph is balanced if the product of the signs of its edges (repetitions included) is positive, and unbalanced otherwise. The unbalanced-girth of a signed graph is the length of a shortest unbalanced closed walk (if such a walk exists). A homomorphism of to is a homomorphism of to

which preserves the balance of closed walks.

In this work, given a signed bipartite graph

of unbalanced-girth , we give a necessary and sufficient condition for to admit a homomorphism from any signed bipartite graph of unbalanced-girth at least whose underlying graph is -minor-free. The condition can be checked in polynomial time with respect to the order of

.

Let

be the signed bipartite graph on vertex set where vertices and are adjacent with a positive edge if their difference is in (where the ’s form the standard basis), and adjacent with a negative edge if their difference is (that is, the all-1 vector). As an application of our work, we prove that every signed bipartite -minor-free graph of unbalanced-girth admits a homomorphism to . This supports a conjecture of Guenin claiming that every signed bipartite planar graph of unbalanced-girth admits a homomorphism to

(this would be an extension of the four-color theorem).

We also give an application of our work to edge-coloring

-regular -minor-free multigraphs.

Added: Jul 8, 2019
Article
Alekseev V. E., Mokeev D. B. Discrete Applied Mathematics. 2016. Vol. 204. P. 1-5.

Given a set X, a König graph G for X is a graph with the following property: for every induced subgraph H of G, the maximum number of vertex-disjoint induced subgraphs from X in H is equal to the minimum number of vertices whose deletion from H results in a graph containing no graph in X as an induced subgraph. The purpose of this paper is to characterize all König graphs for X, where X has only the 3-path or X consists of the 3-path and 3-cycle. We give also polynomial-time algorithms for the recognition of König graphs for the 3-path and for finding the corresponding packing and cover numbers in graphs of this type.

 

 

Added: Nov 12, 2015
Article
Gurvich V., Koshevoy G. Discrete Applied Mathematics. 2018. P. 1-15.

Given two finite ordered sets A and B, let O=A×B denote the set of outcomes of the following game: Two players, Alice and Bob, have the sets of strategies X and Y that consist of all monotone non-decreasing mappings x:A→B and y:B→A, respectively. It is easily seen that each pair (x,y)∈X×Y produces at least one deal, that is, an outcome (a,b)∈O such that x(a)=b and y(b)=a. Denote by G(x,y)⊆O the set of all such deals related to (x,y). The obtained mapping G:X×Y→2O is a game correspondence. Choose an arbitrary deal g(x,y)∈G(x,y) to obtain a mapping g:X×Y→O, which is a game form. We show that each such game form is tight and, hence, Nash-solvable, that is, for any pair u=(uA,uB) of utility functions of Alice and Bob, the obtained monotone bargaining game (g,u) has at least one Nash equilibrium (x,y) in pure strategies. Moreover, |G(x,y)|=1 and, hence, (x,y) is a Nash equilibrium in game (g,u) for all g∈G. We also obtain an efficient algorithm that determines such an equilibrium in time quadratic in |O|, although the numbers of strategies are exponential in |O|. Our results show that, somewhat surprisingly, the players have no need to hide or randomize their bargaining strategies, even in the zero-sum case.

Added: Oct 10, 2018
Article
Ignatov D. I. Discrete Applied Mathematics. 2018. Vol. 249. P. 74-84.

Triadic Formal Concept Analysis (3FCA) was introduced by Lehman and Wille almost two decades ago. Many researchers work in Data Mining and Formal Concept Analysis using the notions of closed sets, Galois and closure operators, and closure systems. However, a proper closure operator for enu- meration of triconcepts, i.e. maximal triadic cliques of tripartite hypergraphs, was not introduced. In this paper, we show that the previously introduced operators for obtaining triconcepts and maximal connected and complete sets (MCCSs) are not always consistent and provide the reader with a definition of valid closure operator and associated set system. Moreover, we study the diffi- culties of related problems from order-theoretic and combinatorial point view as well as provide the reader with justifications of the complexity classes of these problems.

Added: Dec 15, 2017
Article
Gurvich V., Boros E., Milanic M. Discrete Applied Mathematics. 2015.
We consider several graphs classes defined in terms of conditions on cliques and stable sets, including CIS, split, equistable, and other related classes.Wepursue a systematic study of the relations between them. As part of this study, we introduce two generalizations of CIS graphs, obtain a new characterization of split graphs, and a characterization of CIS line graphs.
Added: Mar 11, 2017
Article
Gurvich V., Oudalov V. Discrete Applied Mathematics. 2014. Vol. 167. P. 131-143.

We study existence of Nash equilibria (NE) in pure stationary strategies in n-person positional games with no moves of chance, with perfect information, and with the mean or total effective cost function.

We construct a NE-free three-person game with positive local costs, thus disproving the conjecture suggested in Boros and Gurvich (2003). Still, the following four problems remain open: Whether NE exist in all two-person games with total effective costs such that

(I) all local costs are strictly positive or (II) there are no dicycles of the total cost zero?

Whether NE exist in all n-person games with the terminal (transition-free) cost functions, provided all dicycles form a unique outcome c and

(III) assuming that c is worse than any terminal outcome or (IV) without this assumption?

For n=3 the case (I) (and hence (II)) is answered in the negative. This is the main result of the present paper. For n=2 the case (IV) (and hence (III)) was answered in the positive earlier.

We briefly survey the above and some other negative and positive results on Nash-solvability in pure stationary strategies for the games under consideration.

Added: Oct 22, 2016
Article
Gurvich V., Nhan Bao H. Discrete Applied Mathematics. 2018. Vol. 243. P. 54-72.

Playing impartial games under the normal and misere conventions may differ a lot. However, there are also many "exceptions" for which the normal and misere Sprague-Grundy functions are very similar. The first such example, the game Nim, was considered by Bouton as early as in 1901. In 1976 Conway introduced a large class of such games that he called tame games. Here we introduce a proper subclass, pet games, and a proper superclass, domestic games. For each of these three classes we provide efficiently verifiable characterizations. These games are closely related to another important subclass of the tame games introduced in 2007 by the first author and called miserable games. We show that tame, pet, and domestic games turn into miserable games by "slight modifications" of the definitions. We also show that the sum of miserable games is miserable and find several other classes that respect summation. The developed techniques allow us to prove that very many well-known impartial games fall into classes mentioned above. Such examples include all subtraction games, which are pet; game Euclid, which is miserable (and, hence, tame), as well as many versions of the Wythoff game and Nim, which may be miserable, pet, or domestic.

Added: Feb 7, 2018
Article
Cherkashin Danila, Kulikov A., Andrei Raigorodskii. Discrete Applied Mathematics. 2018. Vol. 243. P. 125-131.

This paper is devoted to the study of the graph sequence Gn = (Vn, En), where Vn is the set of all vectors v ∈ R n with coordinates in {−1, 0, 1} such that |v| = √ 3 and En consists of all pairs of vertices with scalar product 1. We find the exact value of the independence number of Gn. As a corollary we get new lower bounds on χ(R n ) and χ(Qn ) for small values of n.

Added: Aug 6, 2018
Article
Gromova Ekaterina, Plekhanova T. Discrete Applied Mathematics. 2019. Vol. 255. P. 40-55.

In this paper, we consider a general class of cooperative multistage games with random time horizon and discuss the problem of implementing a cooperative solution. It is known that in many cases a cooperative solution can be time-inconsistent and hence not realizable. To solve this problem, the imputation distribution procedure was proposed. However, the computed payment distribution scheme may result in negative payments which are not feasible. In this case, one has to carry out a regularization procedure as described in the paper. We describe a general regularization scheme and apply it both to the core and to the Shapley value. It is shown that for the mentioned two cases the regularization can be carried out in two alternative ways thus providing a basis for developing efficient numerical schemes. For the Shapley value the regularization procedure was elaborated and described in the form of an algorithm. The obtained results are illustrated with two numerical examples.

Added: Oct 8, 2019
Article
Gurvich V., Boros E., Kazuhisa M. et al. Discrete Applied Mathematics. 2018. Vol. 239. P. 1-14.

Moore's generalization of the game of Nim is played as follows. Given two integer parameters $n, k$ such that $1 \leq k \leq n$, and $n$ piles of tokens. Two players take turns. By one move a player reduces at least one and at most $k$ piles. The player who makes the last move wins. The P-positions of this game were characterized by Moore in 1910 and an explicit formula for its Sprague-Grundy function was given by Jenkyns and Mayberry in 1980, for the case $n = k+1$ only. We modify Moore's game and introduce Exact $k$-Nim in which each move reduces exactly $k$ piles. We give a simple polynomial algorithm computing the Sprague-Grundy function of Exact $k$-Nim in case $2k > n$ and an explicit formula for it in case $2k = n$. The last case shows a surprising similarity to Jenkyns and Mayberry's solution even though the meaning of some of the expressions are quite different. On the Sprague-Grundy function of Exact $k$-Nim. Available from: https://www.researchgate.net/publication/281144667_On_the_Sprague-Grundy_function_of_Exact_k-Nim [accessed Oct 26 2017].

Added: Oct 26, 2017
Article
Shabanov D. A., Semenov A. Discrete Applied Mathematics. 2020. Vol. 276. P. 134-154.

The paper deals with weak chromatic numbers of random hypergraphs. Recall that a vertex coloring is said to be j-proper for a hypergraph if every j+1 vertices of any edge do not share a common color. The j-chromatic number of a hypergraph is the minimum number of colors required for a -proper coloring. We study the j-chromatic number of a random hypergraph in the binomial model H(n,k,p) in the case j=k-2 and investigate, for fixed k, the threshold for the property that j-chromatic number of does not exceed r. This threshold corresponds to the sparse case and the main result gives the tight bounds for it.

Added: Oct 31, 2019
Article
Podolskii V. V., Hansen K. A., Ibsen-Jensen R. et al. Discrete Applied Mathematics. 2013. Vol. 161. No. 16-17. P. 2440-2459.

For matrix games we study how small nonzero probability must be used in optimal strategies. We show that for n×n win–lose–draw games (i.e.  (−1,0,1) matrix games) nonzero probabilities smaller than n−O(n)are never needed. We also construct an explicit n×n win–lose game such that the unique optimal strategy uses a nonzero probability as small as n−Ω(n). This is done by constructing an explicit (−1,1)nonsingular n×n matrix, for which the inverse has only nonnegative entries and where some of the entries are of value nΩ(n).

Added: Dec 18, 2014
1 2