?
Combinatorics and Algorithms for Quasi-Chain Graphs
Algorithmica. 2023. Vol. 85. No. 3. P. 642–664.
The class of quasi-chain graphs is an extension of the well-studied class of chain
graphs. This latter class enjoys many nice and important properties, such as bounded
clique-width, implicit representation, well-quasi-ordering by induced subgraphs, etc.
The class of quasi-chain graphs is substantially more complex. In particular, this class
is not well-quasi-ordered by induced subgraphs, and the clique-width is not bounded
in it. In the present paper, we show that the universe of quasi-chain graphs is at least as
complex as the universe of permutations by establishing a bijection between the class
of all permutations and a subclass of quasi-chain graphs.This implies, in particular, that
the induced subgraph isomorphism problem is NP-complete for quasi-chain graphs.
On the other hand, we propose a decomposition theorem for quasi-chain graphs that
implies an implicit representation for graphs in this class and efficient solutions for
some algorithmic problems that are generally intractable.
Mylnikov L., Slivnitsin P., Engineering Applications of Artificial Intelligence 2026 Vol. 179 Article 115185
The paper describes a applied artificial intelligence task of recognition-by-components method of real objects based on the recognition of a limited set of primitives or components. The recognition-by-components makes it possible to determine the components, that compose an object, and increase the number of recognizable objects without degrading the recognition quality. Training is performed on ...
Added: May 29, 2026
Gorbounov Vassily, Kazakov A., Data Analytics and Topology 2025 Vol. 1 No. 1 P. 33–45
A classic problem in data analysis is studying the systems of subsets defined by either a similarity or a dissimilarity function on X which is either observed directly or derived from a data set.
For an electrical network there are two functions on the set of the nodes defined by the resistance matrix and the response ...
Added: May 28, 2026
Mokienko O., Zisman M. A., Bobrov P. et al., American Journal of Physical Medicine and Rehabilitation 2026 Vol. 105 No. 6 P. 555–563
Brain-computer interfaces (BCIs) represent a promising technology for restoring lower limb motor functions and gait after stroke. The application of BCIs in this field is supported by a limited number of studies. The objective of the review was to systematically and critically evaluate the current evidence on the use of BCIs for lower limb function ...
Added: May 28, 2026
М.: Институт проблем управления им. В.А. Трапезникова РАН, 2024.
В сборник вошли материалы VIII Международной научной конференции «Информационные технологии и технические средства управления» (ICCT-2024). На конференции были рассмотрены вопросы, касающиеся перспектив развития научного приборостроения в телекоммуникационных и управляющих системах, биомедицинской информатики, аппаратного и программного обеспечения информационнокоммуникационных систем, надежности, диагностики и неразрушающего контроля, систем управления и автоматизации, цифровых экосистем, управления производством и логистикой, методов математического ...
Added: May 27, 2026
Degtyarev A., Bakhurin S., Yudin N., DSPA 2026 P. 1–6
This paper investigates one possible solution to the problem of self-interference cancellation (SIC) arising in the design of in-band full-duplex (IBFD) communication systems. Self-interference cancellation is performed in the digital domain using multilayer nonlinear models adapted via gradient-based optimization. The presence of local minima and saddle points during the adaptation of multilayer models limits the ...
Added: May 26, 2026
Ilyashenko Y., Shilin I., Stanislav Minkov, Russian Journal of Mathematical Physics 2026 Vol. 33 No. 1 P. 89–106
In this paper, new numerical invariants of structurally unstable vector fields in the plane
are found. One of the main tools is an improved asymptotics of sparkling saddle connections that
occur when a separatrix loop of a hyperbolic saddle breaks. Another main tool is a new topological
invariant of two arithmetic progressions, both perturbed and unperturbed, on the ...
Added: May 26, 2026
Androsov I., Proceedings of the Institute for System Programming of the RAS 2026 Vol. 38 No. 3 P. 87–114
This paper examines echo state networks (ESNs), one of the most prevalent approaches to
implementing reservoir computing. An ESN consists of a recurrent neural network with fixed (untrained)
weights and a readout layer that is typically linear and trainable. This approach enables the creation of energyefficient and computationally efficient neural networks capable of real-time learning. However, since ...
Added: May 26, 2026
Gusev I., Maksaev A., Promyslov V., Journal of Mathematical Sciences 2025 Vol. 299 No. 6
The regular graph of the space of n × m matrices over a field F is defined as the undirected graph whose vertices are matrices of rank min(n, m), and distinct matrices A and B are connected by an edge if and only if rk(A + B) < min(n, m). In this paper, for |F| ...
Added: May 25, 2026
Караваева Е. А., Кулигин Л. А., Rezunik L. et al., Труды Института системного программирования РАН 2026 Т. 38 № 3 С. 67–94
В статье представлен метод рефакторинга исходного кода на основе интеграции большой языковой модели (LLM) и расширенной UML-модели программного кода. Предложенный подход позволяет выявлять проблемные участки кода с использованием функций тревожности и структурных метрик классов, а затем выполнять автоматизированный рефакторинг. Ключевой особенностью метода является использование LLM для генерации формальных спецификаций на языке OCL (Object Constraint Language), ...
Added: May 24, 2026
Tyukin I., Tyukina T., van Helden D. P. et al., Information Sciences 2024 Vol. 678 Article 120856
AI errors pose a significant challenge, hindering real-world applications. This work introduces a novel approach to cope with AI errors using weakly supervised error correctors that guarantee a specific level of error reduction. Our correctors have low computational cost and can be used to decide whether to abstain from making an unsafe classification. We provide ...
Added: May 23, 2026
Zaikin A., Sviridov I., Sosedka A. et al., Technologies 2026 Vol. 14 No. 2 Article 84
High-dimensional tabular data are common in biomedical and clinical research, yet conventional machine learning methods often struggle in such settings due to data scarcity, feature redundancy, and limited generalization. In this study, we systematically evaluate Synolitic Graph Neural Networks (SGNNs), a framework that transforms high-dimensional samples into sample-specific graphs by training ensembles of low-dimensional pairwise ...
Added: May 23, 2026
Chertopolokhov V., Mukhamedov A., Bugriy G. et al., IEEE Access 2026 Vol. 14 P. 14369–14392
This study presents on-the-fly identification and multi-step prediction of nonlinear systems with delayed inputs using a dynamic neural network combined with a smooth projection onto ellipsoids. The projection enforces parameter constraints that guarantee stability, while a Lyapunov–Krasovskii analysis yields computable ultimate error bounds. Riccati-type matrix inequalities are derived, providing an efficient vectorization–projection–devectorization implementation suitable for ...
Added: May 22, 2026
Морозов С. В., Calcolo 2026 Vol. 63 No. 2 Article 23
The approximation of tensors in a low-para metric format is a crucial component in many mathematical modelling and data analysis tasks. Among the widely used low-parametric representations, the canonical polyadic (CP) decomposition is known to be very efficient. Nowadays, most algorithms for CP approximation aim to construct the approximation in the Frobenius norm; however, some ...
Added: May 22, 2026
Loshkareva M. E., Matveeva N., Вестник Томского государственного университета. История 2026 № 100 С. 112–118
This research is an endeavor to apply social network analysis (SNA) to the study of a medieval narrative source. The authors suppose that the use of network analysis may offer new possibilities in the study of the history of regions characterized by some political fragmentation. Authors tried to construct networks of historical interactions from 1193 ...
Added: May 22, 2026
Nadutkina A., Tikhomirov A., Timushev D., Siberian Advances in Mathematics 2024 Vol. 34 No. 2 P. 146–153
We study the spectra of random weighted bipartite graphs. We establish that, under specific assumptions on the edge probabilities, the symmetrized empirical spectral distribution function of the graph’s adjacency matrix converges to the symmetrized Marchenko-Pastur distribution function. ...
Added: January 26, 2026
El-Mesady A., Farahat T., El-Shanawany R. et al., Algorithms 2023 Vol. 16 No. 7 Article 320
Nowadays, graph theory is one of the most exciting fields of mathematics due to the tremendous developments in modern technology, where it is used in many important applications. The orthogonal double cover (𝑂𝐷𝐶) is a branch of graph theory and is considered as a special class of graph decomposition. In this paper, we decompose the complete bipartite ...
Added: July 30, 2023
Grinblat A., Lopatkin V., Journal of Algebra and its Applications 2020 Vol. 20 No. 5 Article 2150083
The aim of this paper is to show that any finite undirected bipartite graph can be considered as a polynomial p∈N[x], and any directed finite bipartite graph can be considered as a polynomial p∈N[x,y], and vise verse. We also show that the multiplication in semirings N[x], N[x,y] correspondences to a operations of the corresponding graphs which looks like a ``perturbed'' ...
Added: September 27, 2021
Alecu B., Atminas A., Loozin V. V. et al., , in: International Workshop on Combinatorial Algorithms, 32nd International Workshop, IWOCA 2021, Ottawa, ON, Canada, July 5–7, 2021Vol. 12757.: Springer, 2021. P. 49–62.
The class of quasi-chain graphs is an extension of the well-studied class of chain graphs. The latter class enjoys many nice and important properties, such as bounded clique-width, implicit representation, well-quasi-ordering by induced subgraphs, etc. The class of quasi-chain graphs is substantially more complex. In particular, this class is
not well-quasi-ordered by induced subgraphs, and the ...
Added: July 1, 2021
Boros E., Gurvich V., Milanic M., Journal of Graph Theory 2020 Vol. 94 No. 3 P. 364–397
A hypergraph is said to be 1-Sperner if for every two hyperedges the smallest of their two set differences is of size one. We present several applications of 1-Sperner hypergraphs to graphs. First, we consider several ways of associating hypergraphs to graphs, namely, vertex cover, clique, independent set, dominating set, and closed neighborhood hypergraphs. For ...
Added: September 7, 2020
Zinder Y., Lazarev A. A., Musatova E. G., Automation and Remote Control 2020 Vol. 81 No. 6 P. 955–966
The paper presents a polynomial-time algorithm for rescheduling traffic when one track of a double-track railway becomes unavailable, the remaining track has a siding, and there are two categories of trains—priority trains such as passenger trains and ordinary trains such as the majority of freight trains. The presented algorithm minimises the negative effect, caused by ...
Added: September 1, 2020
Avdoshin S. M., Набебин А. А., М.: ДМК Пресс, 2019.
The book contains the necessary information from the algorithm theory, graph theory, combinatorics. It is considered partially recursive functions, Turing machines, some versions of the algorithms (associative calculus, the system of substitutions, grammars, Post's productions, Marcov's normal algorithms, operator algorithms). The main types of graphs are described (multigraphs, pseudographs, Eulerian graphs, Hamiltonian graphs, trees, bipartite ...
Added: August 24, 2018
Malyshev D., Discrete Applied Mathematics 2018 Vol. 247 P. 423–432
We show that the weighted coloring problem can be solved for {P5,banner}-free graphs and for {P5,dart}-free graphs in polynomial time on the sum of vertex weights. ...
Added: April 23, 2018
Lozin V. V., Malyshev D., Mosca R. et al., Theoretical Computer Science 2017 Vol. 700 P. 63–74
Weighted independent domination is an NP-hard graph problem, which remains computationally intractable in many restricted graph classes. In particular, the problem is NP-hard in the classes of sat-graphs and chordal graphs. We strengthen these results by showing that the problem is NP-hard in a proper subclass of the intersection of sat-graphs and chordal graphs. On ...
Added: August 28, 2017