?
Vertex coloring of graphs with few obstructions
Discrete Applied Mathematics. 2017. Vol. 216. P. 273–280.
Lozin V. V., Malyshev D.
We study the vertex coloring problem in classes of graphs defined by finitely many forbidden induced subgraphs. Of our special interest are the classes defined by forbidden induced subgraphs with at most 4 vertices. For all but three classes in this family we show either NP-completeness or polynomial-time solvability of the problem. For the remaining three classes we prove fixed-parameter tractability. Moreover, for two of them we give a 3/2 approximation polynomial algorithm.
Language:
English
Publication based on the results of:
Дильмухаметова Алия Мидхатовна, Напалков В. В., «Doklady Mathematics» 2012 Т. 443 № 3 С. 293–295
В данной работе введены обобщенные частные производные, изучены дифференциальные уравнения в обобщенных частных производных с постоянными коэффициентами и доказан фундаментальный принцип Эйлера для таких уравнений. Устанавливлена связь с классом уравнений в обычных частных производных с переменными коэффициентами. ...
Added: September 21, 2026
Springer, Cham, 2025.
Added: September 21, 2026
Aleksei Samarin, Alexander Savelev, Aleksei Toropov et al., Journal of Imaging 2025 Vol. 11 No. 6 P. 1–20
This study presents a unified low-parameter approach to multi-class classification of microorganisms (micrococci, diplococci, streptococci, and bacilli) based on automated machine learning. The method is designed to produce interpretable taxonomic descriptors through analysis of the external geometric characteristics of microorganisms, including cell shape, colony organization, and dynamic behavior in unfixed microscopic scenes. A key advantage ...
Added: September 21, 2026
Springer, 2026.
Two volumes of the SPECOM 2026 proceedings contain a collection of submitted papers presented at SPECOM 2026, which were thoroughly reviewed by members of the Program Committee and additional reviewers consisting of almost 80 experts in the conference topic areas. In total, 65 regular full papers out of 99 submissions made via the EasyChair electronic ...
Added: September 20, 2026
Medvedev V., Annals of Global Analysis and Geometry 2026 Vol. 70 No. 2 P. 8–23
This paper studies three-dimensional compact static manifolds with boundary and positive scalar curvature. We prove that, under a suitable bound on the Ricci curvature, the orientable quotient of the Nariai static manifold with boundary is the only such manifold with connected boundary, provided that the zero-level set of the potential is connected and does not intersect ...
Added: September 19, 2026
Aleksei Samarin, Alexander Savelev, Aleksei Toropov et al., Pattern Recognition and Image Analysis 2026 Vol. 36 No. 2 P. 323–334
In this paper, an improved approach for automatic wildlife detection in natural environments based on the integration of a neural network architecture with a two-stream attention mechanism and a novel preclassification step based on infrared data has been presented. The proposed method addresses one of the key challenges in environmental monitoring: the need for scalable ...
Added: September 19, 2026
Aleksei Samarin, Nazarenko A., Kotenko E. et al., Proceedings of the ACM on Management of Data, USA 2026 Vol. 4 No. 1 P. 1–28
Modern knowledge and large volumes of data are increasingly encoded within neural networks, making the task of simplifying their structures and reducing the number of parameters especially relevant, both to improve efficiency and to facilitate deployment in resource-constrained environments. This paper presents a novel approach to neural network compression that addresses redundancy at both the ...
Added: September 19, 2026
Aleksei Samarin, Alexander Savelev, Aleksei Toropov et al., Pattern Recognition and Image Analysis 2025 Vol. 35 No. 2 P. 148–158
This paper describes our research on creating classifiers for microbial images (micrococci microscopy images) obtained from pictures of unfixed microscopic scenes. In our work, we propose an AutoML approach based on the automatic generation and analysis of the feature space for constructing the most optimal descriptors of microorganism images for subsequent classification. This makes it ...
Added: September 19, 2026
Aleksei Samarin, Alexander Savelev, Aleksei Toropov et al., Pattern Recognition and Image Analysis 2026 Vol. 36 No. 2 P. 302–312
The lack of annotated microscopic datasets remains a major obstacle to training robust deep learning models for microbial classification. In this paper, a novel data augmentation pipeline that uses visual–linguistic large-scale models to generate synthetic microscopic images of six different bacterial and nonbacterial classes has been proposed. Synthetic samples have gradually been added to the ...
Added: September 19, 2026
Springer, Cham, 2026.
computer vision ...
Added: September 19, 2026
Springer, Cham, 2026.
Added: September 19, 2026
Poddiakov A., / Series Social Science Research Network "Social Science Research Network". 2026. No. 7437658.
Clarity of knowledge and reasoning is necessary in many cases. Yet vagueness in scientific thinking related to surprise, curiosity, "ability to engage with not-knowing" (de Freitas) and abductive reasoning is also a crucially important source of scientific creativity which supplements combinatorial logic when dealing with the already known. Starting from studies by C. S. Peirce ...
Added: September 15, 2026
Glutsyuk A., / Series arXiv "math". 2026.
B.Josephson (Nobel Prize, 1973) predicted a tunnelling effect for a system of two superconductors separated by a narrow dielectric (such a system is called Josephson junction): existence of a supercurrent through it and equations governing it. The overdamped Josephson junction is modeled by the family of differential equations on the 2-torus, dθdτ=1ω(cosθ+B+Acosτ), which is known as ...
Added: September 8, 2026
Pochinka O., Shmukler V., / Series math.RT "arXiv:1808.06395 [math.RT]". 2026.
Anosov flows have a long and rich history, firstly motivated by the
study of geodesic flows in negative curvature surface by Anosov and Sinai.
Not every closed manifold admits an Anosov flow for well-known reasons:
the fundamental group of a 3-manifold M admitting an Anosov flow must
have exponential growth, and M must be universally covered by R3. Nevertheless,
there ...
Added: August 31, 2026
Shabanov N., Kuricheva O., Kurbatova J. et al., / Series Working Papers SSRN "Department of Economics Ca’ Foscari University of Venice". 2026.
The carbon balance of an ecosystem is the difference between Gross Primary Productivity (GPP) and Ecosystem Respiration (Reco) as expressed by Net Ecosystem Exchange (NEE). While remote sensing retrievals of GPP have reached maturity, Reco estimation remains underexplored and ultimately cast bias on NEE. Here we present an end-to-end multi-scale analysis of the mechanism of ...
Added: August 21, 2026
Ponomarenko A., / Series Computer Science "arxiv.org". 2025.
This paper addresses the challenge of merging hierarchical navigable small world (HNSW) graphs, a critical operation for distributed systems, incremental indexing, and database compaction. We propose three algorithms for this task: Naive Graph Merge (NGM), Intra Graph Traversal Merge (IGTM), and Cross Graph Traversal Merge (CGTM). These algorithms differ in their approach to vertex selection ...
Added: July 30, 2026
Loubenets E. R., / Series arxiv.org "quant-ph". 2026. No. 2607.18050.
In many quantum applications it is important to know whether or not a Bell nonlocal two-qudit state exhibits its nonlocality under correlation scenarios with some given numbers S1,S2≥1 of generalized quantum measurements at two sites. In the present article, we find analytically a new general locality condition sufficient for a nonseparable Werner state with a ...
Added: July 21, 2026
Bolbachan V., / Series math "arxiv.org". 2024.
Chow polylogarithms are some special functions arising in explicit description of the Beilinson regulator map. The most interesting functional equation for this function reflects its vanishing on the boundary in the Bloch's cycle complex. We show that this functional equation formally follows from more simple ones, namely skew-symmetry, functoriality and multiplicativity.
To prove this, we study ...
Added: July 16, 2026
Bolbachan V., / Series math "arxiv.org". 2024.
Let K be a field of characteristic zero. We prove that its motivic cohomology in degree m−1 and weight m is rationally isomorphic to the cohomology of the polylogarithmic complex. This gives a partial extension of A. Suslin theorem describing the indecomposable K3 of a field. ...
Added: July 16, 2026
Panov V., Ryabchenko A., / Series arXiv "stat.ME". 2026. No. 2607.05048.
This paper investigates the problem of statistical inference for a mixture distribution consisting of a discrete and a continuous component, with a particular focus on the class of rational-infinitely divisible distributions. We consider non-parametric estimation of both components of the mixture as well as the quasi-L{é}vy measure, assuming that the mixture belongs to the class ...
Added: July 9, 2026
Piontkovski D., / Series arXiv "math". 2026.
A noncommutative projective variety is defined, following Artin and Zhang, by a graded coherent algebra 𝐴. The category of coherent sheaves is then the quotient qgr(𝐴) of the category of finitely presented graded modules by the subcategory of torsion modules. We consider the categorical and polynomial entropies of the Serre twist, that is, of the ...
Added: June 23, 2026
Piontkovski D., / Series arXiv "math". 2025.
If a symmetric multilinear algebra is weakly nil, then it is Engel. This result may be regarded as an infinite-dimensional analogue of the well-known Jacobian theorem, which states that if a polynomial mapping has a polynomial inverse, then its Jacobian matrix is invertible. This refines a theorem of Gerstenhaber and partially answers a question posed ...
Added: June 23, 2026
Konakov V., Kucher D., Mammen E., / Series arXiv "math". 2026. No. 2606.11142v1.
In this paper, we construct strong approximations for discrete-time Markov chains weakly converging to continuous diffusion processes, as well as for their perturbed counterparts. Under the assumption of bounded coefficients, we construct closely coupled versions of these processes on a shared probability space. In particular, for both non-degenerate and degenerate cases, we maximize the probability ...
Added: June 11, 2026
Shipilov F., Barnyakov A., Ivanov A. et al., / Series Physics "arxiv.org". 2026.
A fast simulation of the detector response is a vital task in high-energy physics (HEP). Traditional Monte-Carlo methods form the backbone of modern particle physics simulation software but are computationally expensive. We present a machine-learning-based approach to fast simulation of the Focusing Aerogel Ring Imaging Cherenkov (FARICH) detector response. Given a particle track and momentum, ...
Added: May 19, 2026