• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site
Of all publications in the section: 38
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
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. S., 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
Шнурков П. В., Иванов А. В. Дискретная математика. 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
Талецкий Д. С., Малышев Д. С. Дискретная математика. 2018. Т. 30. № 4. С. 115-133.
Added: Dec 12, 2018
Article
Энатская Н. Ю. Дискретная математика. 2017. Т. 29. № 1. С. 126-135.

We describe the ways of representation, indexing and enumeration outcomes from the scheme of the arrangement of distinguishable particles to in distinguishable cells in terms of the graph of passages. We describe same methods of statistical modelling of outcomes of the scheme.

Added: Nov 30, 2017
Article
Ивченко Г. И., Соболева М. В. Дискретная математика. 2011. Т. 23. № 3. С. 23-31.
Added: Apr 12, 2012
Article
Ивченко Г. И., Миронова В. А. Дискретная математика. 2013. Т. 25. № 1. С. 90-110.

We analyse properties of the Walsh spectrum of Boolean functions of n variables which are chosen at random from some subsets of the set of all these functions. We derive the characteristic functions of the spectrum and find exact and asymptotic, as n → ∞, distributions of its various characteristics.

Added: Aug 20, 2013
Article
Вялый М. Н., Вороненко А. А. Дискретная математика. 2016. Т. 28. № 4. С. 50-57.
Added: Jan 13, 2017
1 2