?
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.
Avdoshin S.M., Patrushev K. A., Proceedings of the Institute for System Programming of the RAS 2026 No. 4 часть 2 P. 245–256
The cardinality-constrained Markowitz problem is NP-hard and traditionally solved with commercial MIQP solvers. Following the 2022 export restrictions that rendered both commercial MIQP software and cloud quantum platforms (IBM Quantum, D-Wave Leap) inaccessible from the Russian Federation, practitioners require open-source alternatives. This paper systematically compares three solver families for the discrete mean-variance problem: two open-source ...
Added: August 27, 2026
Zaikin A., Vlasenko D., Zakharov D. et al., Diagnostics 2026 Vol. 16 No. 17 P. 1–15
Background/Objectives: Synolitic graphs (SGs) were developed for task-based fMRI, where
edge weights encode the discriminative power of pairwise regional features; whether similar
information can be recovered from resting-state data was untested. We benchmarked
SGs for autism spectrum disorder (ASD) classification using the multisite ABIDE-I dataset
(871 subjects: 403 subjects with ASD, 468 typical controls; 17 sites; CC200 atlas). Methods:
Using ...
Added: August 27, 2026
Melnikov I., Pelinovsky E., Nonlinear Dynamics 2026 No. 114 Article 934
Pyramidal solitons (solitons with more than two inflection points) of the generalized Korteweg–de Vries (KdV) equation are investigated. Necessary and sufficient conditions for the existence of such structures are presented. Within the framework of the generalized Gardner equation — the simplest model that admits pyramidal solitons as solutions — it is shown that these solutions ...
Added: August 27, 2026
Тула: Тульский государственный педагогический университет им. Л.Н. Толстого, 2025.
Сборник содержит материалы, представленные на XXIV Международной конференции «Алгебра, теория чисел, дискретная геометрия и многомасштабное моделирование: современные проблемы, приложения и проблемы истории», посвящённой 110-летию со дня рождения академика Юрия Владимировича Линника и 110-летию со дня рождения профессора Андрея Борисовича Шидловского и 80-летию со дня рождения профессора Геннадия Ивановича Архипова. Материалы конференции будут полезны научным работникам, ...
Added: August 27, 2026
Nesterenko A., Чирский В. Г., Матвеев В. Ю., Чебышевский сборник 2026 Т. 27 № 2 С. 118–127
The article presents the results of a practical study of the statistical properties of some sequences that are values of functions of a special type. ...
Added: August 26, 2026
Eduard Sopin, Nazarin A., Begishev V. et al., IEEE Transactions on Vehicular Technology 2026 Vol. 75 No. 6 P. 10995–11007
Aimed at rate-greedy applications having extreme requirements for the data rate at the air interface, 5G New Radio (NR) systems may experience problems when the number of user equipment (UE) in the coverage of the cell increases due to limited capacity of the physical downlink control channel (PDCCH).The aim of this study is to explore ...
Added: August 26, 2026
Джонов А. Т., Avdoshin S. M., Информационные технологии 2026 Т. 32 № 8 С. 421–427
This systematic review presents an analysis of the "Vibe Coding" methodology — a contemporary approach to the iterative software development process using Large Language Models (LLMs). Code generation tools are transforming software development by enabling programmers to formulate tasks and describe the desired behavior of software in natural language, while LLMs generate source code corresponding ...
Added: August 25, 2026
Блудов М. В., Journal of Fixed Point Theory and Applications 2026 No. 28 Article 73
In this paper, we study a construction of homotopy invariants of open or closed covers, where the homotopy class is defined relative to a pair (V, r), with V a finite set of points in and r a point in the interior of their convex hull. We show that the simplicial complex of non-balanced subsets associated with (V, r) has the homotopy ...
Added: August 25, 2026
Melman A., Evsyutin O., Journal of the Franklin Institute 2026 Vol. 363 No. 15 Article 109005
Open access to images creates opportunities for violation of the authors' rights. Digital watermarks can be used to securely publish images online. They are invisibly added into the images before publication and can be extracted at any time to verify ownership. However, achieving a balance between embedding imperceptibility and robustness to image processing operations is ...
Added: August 25, 2026
L.I. Kuzmina, Osipov , Y. V., Kolokoltseva, T. N., Advances in Water Resources 2026 Vol. 213 Article 105335
We study 1D transport of mobilized particles, detached from the solid matrix, in porous media (so-called fines migration). Three types of colloidal-suspension flow models are considered: (i) averaged model for multicomponent colloids with distributed properties; (ii) flow of binary colloids with interacting particles; (iii) discrete system for multicomponent low-concentration colloid. These models account for distributed ...
Added: August 25, 2026
Liudmila I. Kuzmina, Osipov, Y. V., International Journal for Computational Civil and Structural Engineering 2026 Vol. 22 No. 2 P. 138–148
Modeling the transport and sedimentation of small particles of suspensions and colloids in porous rocks is an important problem in subsurface hydromechanics. Particles entrained in fluid are transported and retained in the rock pores. The filtration process is determined by the number and size of pores and is characterized by porosity—the ratio of the void ...
Added: August 25, 2026
L.I.Kuzmina, Osipov Y. V., Mathematical notes, ISSN 0001-4346 2025 Vol. 116 No. 6 P. 1251–1261
We consider the displacement of oil by water with active chemical reagents in porous media. A one-dimensional model of reagent transport and deposition is defined by a hyperbolic system of first-order equations. The purpose of the article is to find the conditions for the existence of a continuous solution with discontinuous boundary and initial conditions. ...
Added: August 25, 2026
IEEE, 2026.
It is with great pleasure that we welcome all the participants of the 12th Conference on Control, Decision and Information Technologies (CoDIT 2026) at the Polytechnic University of Bari – Orabona Street 4, 70125 Bari, Italy, July 13-16, 2026. CoDIT has grown to become one of the largest conferences organized in Europe and in the ...
Added: August 24, 2026
Лукьяненко Д. В., Ragimova A., Мухорина А. et al., European Physical Journal: Special Topics 2026 P. 1–24
Electronic health records (EHRs) contain vast volumes of clinical information that encode complex relationships between diseases. Traditional approaches to the analysis of interrelated or co-occurring diseases have focused on pairwise associations between diagnoses, missing the higher-order structures that characterise multimorbid patients. The present paper offers a narrative review of existing statistical, machine-learning, and artificial intelligence ...
Added: August 20, 2026
CEUR-WS.org, 2026.
The second edition of the Generative Code Intelligence Workshop (GeCoIn 2026) was held in conjunction with the 35th International Joint Conference on Artificial Intelligence (IJCAI-ECAI 2026), in Bremen, Germany, August 16, 2026. The workshop arose from the desire to bring together a research community that has, in recent years, witnessed rapid progress in the application ...
Added: August 20, 2026
Ryumina E., Aksenov A., Koryakovskaya D. et al., IEEE Access 2026 Vol. 14 P. 124759–124778
Psychological characteristic estimation from multimodal in-the-wild behavior is usually studied using separate corpora, each annotated for a single target task. Such annotation fragmentation limits cross-task learning and cross-domain generalization across affective, dispositional, and interactional phenomena. To address this problem, we use emotion, apparent personality trait, and ambivalence recognition as representative tasks and introduce MM-PSYCHE, a ...
Added: August 20, 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