?
A complete complexity dichotomy of the edge-coloring problem for all sets of 8-edge forbidden subgraphs
Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций"). 2023. Vol. 17. No. 4. P. 791–801.
Malyshev D., Duginov O. I.
For a given graph, the edge-coloring problem is to minimize the number of colors sufficient to color all the graph edges so that any adjacent edges receive different colors. For all classes defined by sets of forbidden subgraphs, each with 7 edges, the complexity status of this problem is known. In this paper, we obtain a similar result for all sets of 8-edge prohibitions.
Groshev Maksim, Rybakov Petr, Teterin N. et al., Sensors 2026 Article 6171
Manual assessment of soybean yield components, such as pod number, is laborious, time-consuming, and subjective. Existing computer-vision approaches based on object detection or instance segmentation perform poorly on close-range RGB imagery of soybean canopies due to severe occlusions, ambiguous plant boundaries, and the high cost of bounding-box annotation. To address these challenges, we propose a ...
Added: October 7, 2026
Bernardin C., Gonçalves P., Olla S., Mathematical Physics Analysis and Geometry 2024 Vol. 27 No. 7
We consider the macroscopic limit for the space-time density fluctuations in the open symmetric simple exclusion in the quasi-static scaling limit. We prove that the distribution of these fluctuations converge to a gaussian space-time field that is delta correlated in time but with long-range correlations in space. ...
Added: October 6, 2026
Томск: Издательство Томского государственного университета, 2026.
Материалы сборника Шестнадцатой Международной конференции «Новые информационные
технологии в исследовании сложных структур» (Москва, 21–25 сентября 2026 г.) ориентированы на
широкий круг специалистов, работающих на стыке теории информации, системного анализа и
прикладных предметных областей. В издание вошли результаты исследований, посвящённые
моделированию дискретных и стохастических структур управления и связи, разработке
высокопроизводительных вычислительных и телекоммуникационных систем, а также вопросам
цифровой трансформации образования, архитектурно-градостроительного проектирования,
экологического ...
Added: October 6, 2026
Bernardin C., Chhaibi R., Najnudel J. et al., Probability Theory and Related Fields 2026 Vol. 195 P. 1823–1875
We study the celebrated Shiryaev-Wonham filter (Wonham, W.M., in J. Soc. Ind. Appl. Math. 347–369, 1964) in its historical setup, where the hidden Markov jump process has two states. We are interested in the weak noise regime for the observation equation. Interestingly, this becomes a strong noise regime for the filtering equations. Earlier results of ...
Added: October 5, 2026
Ismailov A., Spiridonov V., Успехи математических наук 2026 Т. 81 № 5 С. 183–184
Получена новая формула для цепной дроби Аски–Вильсона в форме отношения двух q-гипер-геометрических рядов. ...
Added: October 5, 2026
Серебренников Д. А., Belov A. V., Информационные технологии и вычислительные системы 2026 № 3 С. 157–169
В условиях роста стоимости энергоресурсов и необходимости повышения энергоэффективности производственных процессов особую актуальность приобретает задача оптимизации энергопотребления промышленных предприятий. В данной работе рассматривается подход к управлению энергозатратами машиностроительного предприятия на основе методов многокритериальной оптимизации. Постановка задачи включает несколько целевых функций: минимизацию энергопотребления, минимизацию стоимости электроэнергии с учётом тарифных ограничений и максимизацию производственной эффективности. Для решения ...
Added: October 5, 2026
Abdulkhaev K., Shirokov D., Advances in Applied Clifford Algebras 2026 Vol. 36 P. 1–21
In this paper, we present explicit formulas for the inverse and determinant in geometric (Clifford) algebras over vector spaces of dimension n = 7. The derivation of these formulas is made possible by generalizing the concept of conjugation to basis conjugation operations. We further develop a general method for constructing such formulas over odd-dimensional spaces ...
Added: October 4, 2026
Kuninets A., IEEE Transactions on Information Theory 2026 P. 1–1
In this work we study the applicability of Quasi-Cyclic Subfield Subcodes of Dual Elliptic (QC-SSDE) codes for integration into code-based cryptographic schemes. Detailed algorithms are provided for constructing parity-check matrices as well as block-circulant parity-check matrices for this family of codes, accompanied by empirical results that enable the construction of QC-SSDE codes with predetermined dimensions. ...
Added: October 3, 2026
Zykov S. V., Уфимцев Г. А., Моделирование, оптимизация и информационные технологии 2026 Т. 14 № 8 С. 1–13
Информационные системы формируют большие объёмы событийных журналов, которые используются для анализа работы приложений и сервисов. При этом события могут поступать в аналитический контур позже момента их фактического возникновения и не в исходном порядке. Такая рассинхронизация приводит к ошибкам при построении агрегированных временных показателей, а регулярный полный пересчёт многомерного аналитического куба требует значительных вычислительных затрат. Целью ...
Added: October 2, 2026
Polarization of opinions in the group: a modeling algorithm considering the dynamics of social bonds
Chebotarev V., Andreyuk D., Elizarova Anastasiya et al., Procedia Computer Science 2022 Vol. 213 No. C P. 596–601
The dynamics of opinion in a group are of interest for a number of practical purposes. In particular, consensus helps and polarization of opinions hinders cohesive teamwork. Existing approaches for modeling opinion dynamics mostly do not take into account the dynamism of social relations in a group. This paper proposes an algorithm and a program ...
Added: October 2, 2026
Konstantinov A., Elizarova Anastasiya P., Utkin L., Computing, Telecommunications and Control 2026 Vol. 19 No. 1 P. 16–25
Decision trees and their ensemble extensions, such as random forests, are widely used as classification models due to their simplicity and interpretability. However, in many real-world tasks where class labels overlap in the feature space, standard decision trees rely on hard splits that create fragile decision boundaries. In these regions, small perturbations in the input ...
Added: October 2, 2026
Medvedev G., Alexandrov Artem, Physical Review E - Statistical, Nonlinear, and Soft Matter Physics 2026 Vol. 114 Article 044102
Graphons are measurable functions used to describe the asymptotic behavior of convergent graph families. Originally motivated by problems in combinatorics and graph theory, graphons have found numerous applications in the modeling and analysis of dynamical processes on networks. In this work, we use graphons to formulate the Ising model on convergent graph sequences, which include ...
Added: October 2, 2026
Kirill V. Kaymakov, Dmitry S. Malyshev, Optimization Letters 2024 Vol. 18 P. 1273–1283
For given edge-capacitated connected graph and two its vertices s and t, the bottleneck (or max min ) path problem is to find the maximum value of path-minimum edge capacities among all paths, connecting s and t. It can be generalized by finding the bottleneck values between s and all possible t. These problems arise ...
Added: April 18, 2024
Gerasimova O., Makarov I., Severin N., IEEE Access 2023 Vol. 11 P. 88074–88086
The problem of query answering over incomplete attributed graph data is a challenging field of database management systems and artificial intelligence. When there are rules on data structure expressed in the form of the ontology, the theoretical complexity of finding exact solution satisfying ontology constraints increases. Logic-based methods use theoretical constructions to obtain efficient rewritings ...
Added: January 5, 2024
Sergei Valentinovich Fedorenko, IEEE Access 2023 Vol. 11 P. 62771–62779
The novel methods for binary discrete Fourier transform (DFT) computation over the finite field have been proposed. The methods are based on a binary trace calculation over the finite field and use the cyclotomic DFT. The direct DFT computational complexity has been reduced due to using the binary trace function over the finite field and ...
Added: July 19, 2023
Complexity function and complexity of validity of modal and superintuitionistic propositional logics
Rybakov M., Shkatov D., Journal of Logic and Computation 2023 Vol. 33 No. 7 P. 1566–1595
We consider the relationship between the algorithmic properties of the validity problem for a modal or superintuitionistic propositional logic and the size of the smallest Kripke countermodels for non-theorems of the logic. We establish the existence, for every degree of unsolvability, of a propositional logic whose validity problem belongs to the degree and whose every ...
Added: January 6, 2023
Malyshev D., Duginov O. I., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2022 Vol. 16 P. 276–291
The edge-coloring problem is to minimize the number of colors sufficient to color all the edges of a given graph so that any adjacent edges receive distinct colors. The complexity status of this problem is known for all the classes defined by the sets of forbidden subgraphs with 7 edges each. In this paper, we ...
Added: December 31, 2022
G. S. Dakhno, D. S. Malyshev, Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2023 Vol. 17 No. 1 P. 25–31
A hereditary class is a set of simple graphs closed under deletion of vertices; every such class is defined by the set of its minimal forbidden induced subgraphs. If this set is finite, then the class is said to be finitely defined. The concept of a boundary class is a useful tool for the analysis ...
Added: December 6, 2022
Kochergin V., Moscow University Mathematics Bulletin 2022 Vol. 77 No. 3 P. 113–119
Abstract: The computational complexity of the element (Formula presented.) of the Abelian group (Formula presented.) (it is supposed that kii for all i) and the computational complexity of the term (Formula presented.) are compared in the paper. The computational complexity means the minimal possible number of multiplication operations, and all the results of intermediate multiplications ...
Added: October 29, 2022
Rybakov M., Shkatov D., Theoretical Computer Science 2022 Vol. 925 P. 45–60
We prove that branching-time temporal logics CTL and CTL* are polynomial-time embeddable into their single-variable fragments. It follows that satisfiability for CTL and CTL*, and therefore also for alternating-time temporal logics ATL and ATL*, in languages with one propositional variable is as algorithmically hard as satisfiability for the full logic: EXPTIME-complete for CTL and ATL, and 2EXPTIME-complete for CTL* and ATL*. We discuss applicability of the technique used in the proofs to other ...
Added: May 12, 2022
Malyshev D. S., Приставченко О. В., Optimization Letters 2022 Vol. 16 P. 1403–1409
The vertex 3-colourability problem is to decide whether the vertex set of a given graph
can be split into three subsets of pairwise non-adjacent vertices. This problem is known
to be NP-complete in a certain class of graphs, defined by an explicit description of
allowed 5-vertex induced subgraphs in them. In the present paper, we improve this
result by ...
Added: February 25, 2022
Rubtsov A. A., Vyalyi M., Information and Computation 2021 Vol. 281 Article 104797
We consider a computational model which is known as set automata. The set automata are one-way finite automata with additional storage-the set. There are two kinds of set automata-deterministic (DSA's) and nondeterministic (NSA's). The model was introduced by Kutrib, Malcher, Wendlandt in 2014. It was shown that DSA-recognizable languages look similar to DCFL's and NSA-recognizable ...
Added: February 2, 2022
Zakharyaschev M., Kontchakov R., Ryzhikov V. et al., The International Joint Conference on Artificial Intelligence (IJCAI), 2020.
Traditionally, description logic has focused on represent- ing and reasoning about classes rather than relations (roles), which has been justified by the deterioration of the computa- tional properties if expressive role inclusions are added. The situation is even worse in the temporalised setting, where monodicity is viewed as an almost necessary condition for decidability. We ...
Added: November 6, 2021
Zhuk D., , in: 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS).: [б.и.], 2021. P. 1–7.
The Surjective Constraint Satisfaction Problem (SCSP) is the problem of deciding whether there exists a surjective assignment to a set of variables subject to some specified constraints, where a surjective assignment is an assignment containing all elements of the domain. In this paper we show that the most famous SCSP, called No-Rainbow Problem, is NP-Hard. ...
Added: September 8, 2021