• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site
Of all publications in the section: 44
Sort:
by name
by year
Article
Sirotkin D., Malyshev D. Discrete Mathematics and Applications. 2018. Vol. 28. No. 4. P. 249-258.

The independent set problem for a given simple graph is to determine the size of a maximal set of its pairwise non-adjacent vertices. We propose a new way of graph reduction leading to a new proof of the NP-completeness of the independent set problem in the class of planar graphs and to the proof of NPcompleteness of this problem in the class of planar graphs having only triangular internal facets of maximal vertex degree 18  

Added: Aug 22, 2018
Article
Chirskii V., Nesterenko A. Discrete Mathematics and Applications. 2017. Vol. 27. No. 1. P. 1-7.

We consider a periodic sequence { ck }k=0 ∞ and investigate a numerical properties of an irrational number α =σk=0 ∞ ck/k!. As an application of our results we present a simple transformation of periodic sequence { ck }k=0 ∞ into aperiodic sequence. 

Added: May 21, 2017
Article
Malyshev D. Discrete Mathematics and Applications. 2017. Vol. 27. No. 2. P. 97-101.
Added: May 10, 2017
Article
Voronenko A. A., Mikhail N. Vyalyi. Discrete Mathematics and Applications. 2017. P. 319-324.

The paper puts forward a nontrivial lower estimate 13n/6 or the cardinality of the domain of a universal function for the class of linear Boolean functions, where n is the number of variables.for the cardinality of the domain of a universal function for the class of linear Boolean functions, where n is the number of variables.

 

Added: Oct 16, 2017
Article
Kochergin Vadim V. Discrete Mathematics and Applications. 2017. Vol. 27. No. 2. P. 81-95.

Let a finite Abelian multiplicative group G be specified by the basis B = {a1, a2, …, aq}, that is, the group G is decomposed into a direct product of cyclic subgroups generated by the elements of the set B: G = 〈a1〉 × 〈a2〉 × … × 〈aq〉. The complexity L(g;B) of an element g of the group G in the basis B is defined as the minimum number of multiplication operations required to compute the element g given the basis B (it is allowed to use the results of intermediate computations many times). Let L(G, B) = maxg∈G L(g; B), LM(G) = maxB L(G, B), Lm(G)= minB L(G, B), M(n) = maxG:|G|≤n LM(G), m(n) = maxG:|G|≤n Lm(G), Mav(n) = (∑G:|G|=nLM(G))/A(n),mav(n)=(∑G:|G|=nLm(G))/A(n), where A(n) is the number of Abelian groups of order n. In this work the asymptotic estimates for the quantities L(G, B), M(n), m(n), Mav(n), and mav(n) are established.

Added: Oct 8, 2018
Article
Zhuk D. Discrete Mathematics and Applications. 2010. Vol. 20. No. 3. P. 337-355.

We consider systems of the form M = F ∪ ν, where F is some Post class and ν is a finite system of definite automata. We divide the Post classes into those for which the problem of A-completeness of such systems of definite automata is algorithmically decidable and those for which the problem of A-completeness is algorithmically undecidable.

Added: Jun 12, 2020
Article
Malyshev D. Discrete Mathematics and Applications. 2009. Vol. 19. No. 6. P. 619-625.
Added: Oct 13, 2010
Article
Malyshev D. Discrete Mathematics and Applications. 2010. Vol. 19. No. 6. P. 625-630.

The notion of a boundary class is a useful notion in the investigation of the complexity of extremal problems on graphs. One boundary class is known for the independent set problem and three boundary classes are known for the dominating set problem. In this paper it is proved that the set of boundary classes for the 3-colouring problem is infinite.

Added: Nov 25, 2012
Article
Taletskii D., Malyshev D. Discrete Mathematics and Applications. 2017. Vol. 27. No. 5. P. 311-318.

We investigate the number of maximal independent sets in q-ary trees of height n, when q is fixed and n tends to infinity.

Added: Oct 14, 2017
Article
Matveenko V. D. Discrete Mathematics and Applications. 2009. No. 19 (4). P. 389-409.
Added: Jan 25, 2010
Article
Kochergin Vadim V., Mikhailovich Anna V. Discrete Mathematics and Applications. 2017. Vol. 27. No. 5. P. 295-302.

The paper is concerned with the complexity of realization of 𝑘-valued logic functions by logic circuits over an infinite complete bases containing all monotone functions; the weight of monotone functions (the cost of use) is assumed to be 0. The complexity problem of realizations of Boolean functions over a basis having negation as the only nonmonotone element was completely solved by A. A. Markov. In 1957 he showed that the minimum number of NOT gates sufficient for realization of any Boolean function 𝑓 (the inversion complexity of the function 𝑓) is ]log_2(𝑑(𝑓) + 1)[. Here 𝑑(𝑓) is the maximum number of the changes of the function 𝑓 from larger to smaller values over all increasing chains of tuples of variables values. In the present paper, Markov’s result is extended to the case of realization of 𝑘-valued logic functions. We show that the minimum number of Post negations (that is, functions of the form 𝑥 + 1 (mod 𝑘)) that is sufficient to realize an arbitrary function of 𝑘-valued logic is ]log_2(𝑑(𝑓) + 1)[ and the minimum number of Łukasiewicz negation (that is, functions of the form 𝑘 − 1 − 𝑥) that is sufficient to realize an arbitrary 𝑘-valued logic function is ]log_𝑘(𝑑(𝑓)+1)[. In addition, another classical Markov’s result on the inversion complexity of systems of Boolean functions is extended to the setting of systems of functions of 𝑘-valued logic.

Added: Mar 14, 2018
Article
Taletskii D., Malyshev D. Discrete Mathematics and Applications. 2020. Vol. 30. No. 1. P. 53-67.

For any n, in the set of n-vertex trees such that any two leaves have no common adjacent vertex, we describe the trees with the smallest number of maximal independent sets.

Added: Feb 12, 2020
Article
Шнурков П. В., Иванов А. В. Дискретная математика. 2014. Т. 26. № 1. С. 143-154.
Added: Jan 30, 2014
Article
М.В. Соболева Дискретная математика. 2012. Т. 24. № 1. С. 123-131.
Added: Feb 25, 2013
Article
Логачев О. А., Федоров С. Н., Ященко В. В. Дискретная математика. 2018. Т. 30. № 1. С. 39-55.
Added: Dec 12, 2018
Article
Бежаева З. И., Оселедец В. И. Дискретная математика. 2012. Т. 24. № 1. С. 108-122.
Added: May 21, 2012
Article
Миронкин В. О. Дискретная математика. 2019. Т. 31. № 4. С. 38-52.

The probabilistic characteristics of the graph of  k-fold iteration of uniform random mapping are studied. Formulas for the distribution of the length of the aperiodicity segment of a arbitrary vertex with some  restrictions are calculated. Exact  expressions  for the probability  of  belonging of two arbitrary vertices to a single connected component,  of hitting by a arbitrary vertex the preimage set of another  vertex and of occurrence of a collision in such graph are obtained.

Added: Dec 8, 2019