?
Analysis of the impact of the number of edges in connected graphs on the computational complexity of the independent set problem
Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций"). 2012. Vol. 6. No. 1. P. 97–99.
Under study is the complexity status of the independent set problem in a class of connected graphs that are defined by functional constraints on the number of edges depending on the number of vertices. For every natural number C, this problem is shown to be polynomially solvable in the class of graphs, On the other hand, this problem is proved to be not polynomially solvable in the class of graphs, for every unbounded nondecreasing function f(n): ℕ → ℕ, such that exponent of this function grows faster than a polynomial function of n. The latter result is true if there does not exist a subexponential algorithm for solving the independent set problem.
Language:
English
Lebedev V., Journal of Mathematical Analysis and Applications 2026 Vol. 563 No. 2 Article 130787
It is known that for every continuous real-valued
function $f$ on the circle $\mathbb T=\mathbb R/2\pi\mathbb Z$ there exists a
change of variable, i.e., a self-homeomorphism $h$ of $\mathbb T$, such that
the superposition $f\circ h$ is in the Sobolev space $W_2^{1/2}(\mathbb T)$.
We obtain new results on simultaneous improvement of functions by a single
change of variable in relation ...
Added: May 14, 2026
Neal N. X., Weiqing L., Dacheng H. et al., Algorithms 2026 Vol. 19 No. 5 P. 1–22
In the era of data-driven education, educational social networks generate large volumes of high-dimensional and complex-structured data through learner interactions, collaborative activities, and resource-sharing behaviors, posing significant challenges to traditional unsupervised learning methods. Such data often exhibit non-convex distributions, heterogeneity, and noise sensitivity, making conventional clustering approaches insufficient for capturing their intrinsic structural relationships. To ...
Added: May 13, 2026
Blokh A., Oversteegen L., Selinger N. et al., Arnold Mathematical Journal 2025 Vol. 12 No. 1 P. 1–40
We describe a model for the boundary of the connectedness locus of the parameter space of cubic symmetric polynomials. We show that there exists a monotone continuous function from the connectedness locus to the model which is a homeomorphism if the former is locally connected. ...
Added: May 13, 2026
Velichkov B., Nikolova-Koleva I., Slavcheva M., Shumen: INCOMA Ltd, 2025.
The RANLP 2025 Student Research Workshop (RANLPStud’2025) is a special track of the established international conference Recent Advances in Natural Language Processing (RANLP’2025).
The RANLPStud is being organised for the 9th time and this year is running in parallel with the other tracks of the main RANLP 2025 conference. The target of RANLPStud’25 is to be a ...
Added: May 12, 2026
Petrov I., Автоматика и телемеханика 2026 № 6 С. 82–118
Системам связанных агентов и сетевому управлению посвящено большое число отечественных и зарубежных исследований. Исторически, наибольший интерес в теории управления возникал к усредняющим системам и, в частности, к задаче консенсуса. Однако сетевое взаимодействие может характеризоваться более специфическими функциями, отражающими зависимость от действий соседей по сети, что особенно явно проявляется в моделях стратегического взаимодействия на сети, которое ...
Added: May 12, 2026
Stepanyants V., Долгов И. М., Хорошилов Г. С. et al., Труды Института системного программирования РАН 2026 Т. 38 № 3 С. 95–110
Highly automated and connected vehicles are gradually entering the market. Currently, solutions are being proposed that allow these technologies to be used for cooperative driving automation, which can significantly improve traffic safety. Such technologies and their software should be tested to ensure safety before being implemented in real systems. Verification and validation of vehicular control ...
Added: May 12, 2026
Tikhonov R., Efendiev M. T., Fedotenkov A. A., 2026 International Russian Smart Industry Conference (SmartIndustryCon) 2026 P. 542–547
High-fidelity simulation environments like CARLA and ROS are essential for connected and automated vehicle research. They allow researchers to verify and validate new software and technology without the time, financial, and safety overheads of real-world testing. However, their operation requires considerable expertise for creating platform-specific scenario configuration files, which complicates the research workflow. This paper ...
Added: May 11, 2026
М.: ООО «Макс Пресс», 2026.
В настоящем сборнике представлены тезисы докладов участников семинара "Интеграция основного и дополнительного физико-математического образования", проходившего 11 февраля 2026 года в ГБОУ Школа №2007 ФМШ г. москвы, а также другие публикации, посвящённые вопросам дополнительного физико-математического образования. ...
Added: May 11, 2026
Novikov R., Sivkin V., Inverse Problems 2026 Vol. 42 No. 4 Article 045009
We consider a plane wave, a radiation solution, and the sum of these solutions (total solution) for
the Helmholtz equation in an exterior region in Rd, d ⩾ 2. In this region, we consider a hyperplane X with sufficiently large distance s from the origin in Rd. We give two-point local formulas
for approximate recovering the radiation ...
Added: May 11, 2026
Hecht M., Hofmann P., Wicaksono D. et al., IMA Journal of Numerical Analysis 2026 Vol. 00 P. 1–30
Recent advances in Bernstein—Walsh theory have extended Bernstein’s Theorem to multiple dimensions, stating that a multivariate function can be approximated with a geometric rate in a downward-closed polynomial space if and only if it is analytic in a generalized Bernstein polyellipse. To compute approximations of this class of functions—which we term Bos–Levenberg–Trefethen–(BLT) functions—we extend the ...
Added: May 11, 2026
Los Alamitos: IEEE Computer Society, 2026.
It is a great pleasure for us to welcome you on behalf of the conference committees, to the 11th IEEE International Conference on Smart Cloud (IEEE SmartCloud 2026), we are glad that we can have this international conference in New York city, USA. Now, please allow us to introduce the IEEE SmartCloud 2026 conference. The ...
Added: May 10, 2026
Avdoshin S. M., Pesotskaya E. Y., Информационные технологии 2026 Т. 32 № 4 С. 185–194
With the rapid advancement of artificial intelligence, and deep learning in particular, models have emerged that are capable of delivering highly accurate predictions. However, the internal logic of such models remains difficult to interpret—an issue of critical importance, especially in domains where the correctness of an algorithm directly affects high-stakes decision-making. One promising avenue for ...
Added: May 8, 2026
Avdoshin S. M., Pesotskaya E. Y., Business Informatics 2026 Vol. 20 No. 1 P. 7–28
The rapid development of artificial intelligence (AI) is accompanied by increasing computational
complexity and decreasing model transparency, which significantly limits its adoption in critical
domains that require a high level of trust, interpretability, and justification of decisions. Under these
conditions, the field of Explainable Artificial Intelligence (XAI) has gained particular importance as it
focuses on approaches and technologies that ...
Added: May 8, 2026
Varnavsky A., IEEE Access 2026 Vol. 14 P. 37487–37508
Puzzles are an excellent tool for learning computer science and programming, fostering increased interest, engagement, and motivation among students, as well as developing logical, critical, and computational thinking. Among beginner programmers, Parson's Programming Puzzles are quite popular, aimed at mastering the basic syntactic and logical constructs of programming languages. However, as students' skills grow, their ...
Added: May 7, 2026
Ismagilov T., Mukosey A., Smirnov F. et al., International Journal of High Performance Computing Applications 2026 Vol. 40 No. 2 P. 240–253
One of the most important aspects of supercomputer development in the post-Moore era is the interconnect technologies that allow one to unite a multitude of processing elements into a well-synchronized computing system. Novel types of supercomputer interconnect require careful benchmarking and compliance with the requirements of modern hardware trends. GPU-based heterogeneous computing is one of ...
Added: May 7, 2026
Kelbert M., Kalimulina E. Y., Entropy 2026 Vol. 28 Article 536
We study binary hypothesis testing for i.i.d. observations under a multiplicative context
weight. For the optimal weighted total loss, defined as the sum of weighted type-I and typeII losses, we prove the logarithmic asymptotic L∗n = exp{−nDwC (P,Q) + o(n)}, n →∞, where Dw
C is the weighted Chernoff information. The single-letter form of the exponent
relies on ...
Added: May 7, 2026
Белоусов Н. М., Черепанов Л. К., Деркачов С. Э. et al., Selecta Mathematica, New Series 2026 Vol. 32 Article 44
We prove equivalence of two integral representations for the wave functions of hyperbolic Calogero–Sutherland system. For this we study two families of Baxter operators related to hyperbolic Calogero–Sutherland and rational Ruijsenaars models; the first one as a limit from hyperbolic Ruijsenaars system, while the second one independently. Besides, computing asymptotics of integral representations and also ...
Added: May 6, 2026
Taletskii D., / Series arXiv "math". 2026.
A vertex subset of a graph is called a \textit{distance-$k$ independent set} if the distance between any two of its distinct vertices is at least $k + 1$. For all $n,k \geq 1$, we determine the minimum possible number of inclusion-wise maximal distance-$k$ independent sets among all $n$-vertex trees. It equals~$n$ if $n \leq k ...
Added: May 1, 2026
Ovcharenko M., / Series arXiv "math". 2026.
We introduce an explicit class of tempered Laurent polynomials in the sense of Villegas and Doran--Kerr in n⩽4 variables including all Landau--Ginzburg models for smooth Fano threefolds with very ample anticanonical class. We check that it contains Landau--Ginzburg models for various Fano fourfolds which are complete intersections in smooth toric varieties and Grassmannians of planes, ...
Added: April 30, 2026
Derkacheva A., Sakirkina M., Kraev G. et al., /. 2026.
Comprehensive data on natural hazards and their consequences are crucial for effective for risk assessment, adaptation planning, and emergency response. However, many countries face challenges with fragmented, inconsistent, and inaccessible data, particularly regarding local-scale events. To address this data gap in Russia, we developed an end-to-end processing pipeline that scrapes news from various online sources, ...
Added: April 28, 2026
Qin X., Deng Y., Shchur L. et al., / Series arXiv "math". 2026. No. 2603.02962.
We perform a Monte Carlo analysis of the Ising model on many three-dimensional lattices. By means of finite-size scaling we obtain the critical points and determine the scaling dimensions. As expected, the critical exponents agree with the three-dimensional Ising universality class for all models. The irrelevant field, as revealed by the correction-to-scaling amplitudes, appears to ...
Added: April 20, 2026
Pilé I., Deng Y., Shchur L., / Series arXiv "math". 2026. No. 2604.10254.
We investigate the spatial overlap of successive spin configurations in Markov chain Monte Carlo simulations using the local Metropolis algorithm and the Svendsen-Wang and Wolff cluster algorithms. We examine the dynamics of these algorithms for two models in different universality classes: the Ising model and the Potts model with three components. The overlap of two ...
Added: April 20, 2026
Zlotnik Alexander, / Series arXiv "math". 2026. No. 2602.03481v1.
We deal with the global in time weak solutions to the 1D compressible Navier-Stokes system of equations for large discontinuous initial data and nonhomogeneous boundary conditions of three standard types. We prove the Lipschitz-type continuous dependence of the solution $(\eta,u,\theta)$, in a norm slightly stronger than $L^{2,\infty}(Q)\times L^2(Q)\times L^2(Q)$, on the initial data $(\eta^0,u^0,e^0)$ in a ...
Added: April 18, 2026
Medvedev V., / Series arXiv "math". 2026.
We investigate the interplay between the dimension of the space of static potentials and the geometric and topological structure of the underlying static three-manifold. A partial classification of boundaryless static manifolds is obtained in terms of this dimension. We also treat the case of static manifolds with boundary. In particular, we prove that if a ...
Added: April 3, 2026