?
Эффективная раскраска графа с помощью битовых операций
Информационные технологии. 2015. № 7. С. 488–494.
Komosko L. F., Batsyn M. V.
Graph coloring problem is one of the classical combinatorial optimization problems. This problem consists in finding the minimal number of colors in which it is possible to color vertices of a graph so that any two adjacent vertices are colored in different colors. The graph coloring problem has a wide variety of applications including timetabling problems, processor register allocation problems, frequency assignment problems, data clustering problems, traffic signal phasing problems, maximum clique problem, maximum independent set problem, minimum vertex cover problem and others. In this paper a new efficient heuristic algorithm for the graph coloring problem is presented. The suggested algorithm builds the same coloring of a graph as does the widely used greedy sequential algorithm in which at every step the current vertex is colored into minimal feasible color. Computational experiments show that the presented algorithm performs graph coloring much faster in comparison with the standard greedy algorithm. The speedup reaches 5,6 times for DIMACS graphs.
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
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
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
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
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
Gabdullin N., Androsov I., / Series Computer Science "arxiv.org". 2026.
Label prediction in neural networks (NNs) has O(n) complexity proportional to the number of classes. This holds true for classification using fully connected layers and cosine similarity with some set of class prototypes. In this paper we show that if NN latent space (LS) geometry is known and possesses specific properties, label prediction complexity can ...
Added: April 2, 2026
Sorokin K., Beketov M., Онучин А. et al., / arxiv.org. Серия cs.SI "Social and Information Networks ". 2025.
Community detection in complex networks is a fundamental problem, open to new approaches in various scientific settings. We introduce a novel community detection method, based on Ricci flow on graphs. Our technique iteratively updates edge weights (their metric lengths) according to their (combinatorial) Foster version of Ricci curvature computed from effective resistance distance between the ...
Added: January 15, 2026
Petrovanov I., Sergeev A., / Series Computer Science "arxiv.org". 2025. No. 2512.18332.
Transport coding reduces message delay in packet-switched networks by introducing controlled redundancy at the transport layer: original packets are encoded into coded packets, and the message is reconstructed after the first successful deliveries, effectively shifting latency from the maximum packet delay to the -th order statistic. We present a concise, reproducible discrete-event implementation of transport coding in OMNeT++, including ...
Added: December 24, 2025
Hessian-based lightweight neural network for brain vessel segmentation on a minimal training dataset
Меньшиков И. А., Бернадотт А. К., Elvimov N. S., / Series arXie "Statistical mechanics". 2025.
Accurate segmentation of blood vessels in brain magnetic resonance angiography (MRA) is essential for successful surgical procedures, such as aneurysm repair or bypass surgery. Currently, annotation is primarily performed through manual segmentation or classical methods, such as the Frangi filter, which often lack sufficient accuracy. Neural networks have emerged as powerful tools for medical image ...
Added: December 1, 2025
Martinez-Saito M., Algorithms 2025 Vol. 18 No. 12 Article 741
Detecting trajectories of hierarchical structures in a dynamical system of multiple interacting particles is an open problem that is typically addressed by imposing strong constraints on the structures to be found. Here, we describe BUNCH, a dynamical filtering algorithm that can efficiently and on-the-fly fit dynamical trajectories of multiple particles to a tree structure of ...
Added: December 1, 2025
Nazarovskiy E., Rustamkhanova G., Сборник материалов студенческой научно-практической конференции имени Льва Львовича Любимова 2023 С. 128–132
На настоящий день дискретная математика играет существенную роль в изучении высшей математики в вузах. Одной из основополагающих тем курса является теория графов, которая широко применяется при решении экономических и управленческих задач, в программировании и других областях. С помощью теории графов можно решить множество задач. Классическим примером такой задачи является раскраска графов. ...
Added: November 30, 2025
Rubchinskiy A., Chubarova D., / Series WP7 "Математические методы анализа решений в экономике, бизнесе и политике". 2025. No. WP7/2025/01.
The article examines one of the most famous examples of socio-economic systems, characterized by significant uncertainty – the S&P-500 stock market, where shares of 500 largest US companies are traded. No assumptions are made about the probabilistic characteristics of the stock market. A flexible algorithm for daily trading has been developed, based on both known fixed data ...
Added: November 9, 2025
Ilyin A., Закон 2024 № 9 С. 91–98
Every serious lawyer in his professional life is faced with a situation when, coming into contact with unknown legal matter in his work, revealing the hidden meaning of legal norms or legal institutions, he finds an unexpected way out of the impasse, discovering something new in law. Is such an expert analytical work of a ...
Added: September 26, 2024
Kham T., Вестник Томского государственного университета. Философия. Социология. Политология 2022 № 65 С. 37–50
The problems of automation of research activities are considered, primarily from the perspective of the epistemic potential of gaining new scientific knowledge without the participation of a human as a subject of science. The bases of automation are considered from the standpoint of jointly working methodological approaches to cognition: empiricism and logical positivism. The author ...
Added: July 30, 2022
Sulimov P., Kertesz-Farkas A., Journal of Proteome Research 2020 No. 19(4) P. 1481–1490
Peptide-spectrum-match (PSM) scores used in database searching are calibrated to spectrum- or spectrum-peptide-specific null distributions. Some calibration methods rely on specific assumptions and use analytical models (e.g., binomial distributions), whereas other methods utilize exact empirical null distributions. The former may be inaccurate because of unjustified assumptions, while the latter are accurate, albeit computationally exhaustive. Here, ...
Added: June 29, 2020
Galatenko A. V., Nersisyan S., Pankratieva V., , in: Proceedings of the International Workshop "What can FCA do for Artificial Intelligence?" (FCA4AI at IJCAI/ECAI 2019).: [б.и.], 2019. P. 65–74.
nterval pattern concepts are a particular case of patternstructures. They can be used to clusterize rows of a numerical formalcontext (data matrix): two rows are close to each other if their entriesat the corresponding positions fall within a given interval.The problem of mining interval pattern concepts has much in commonwith the known problem related to ...
Added: April 28, 2020
Lokshin I., Политическая экспертиза: ПОЛИТЭКС 2019 Т. 15 № 1 С. 45–58
The paper makes an attempt at inserting (positivistic) political science in a broader epistemological
context than it is usually conceived. The implied context is that of the contingency of the
human world which was pointed out by Aristotle in “Nicomachean Ethics” when he stated that
politics deals more with particulars than with general principles, and more with changeable ...
Added: October 29, 2019
Kiselev S., Cherkashin D., / Series arXiv "math". 2019.
We consider a family of distance graphs in R n and find its independent numbers in some cases. Define graph J±(n, k, t) in the following way: the vertex set consists of all vectors from {−1, 0, 1} n with k nonzero coordinates; edges connect the pairs of vertices with scalar product t. We find ...
Added: October 21, 2019
Максимова Елизавета Андреевна, В кн.: Системное моделирование социально-экономических процессов: труды 40-й Международной научной школы-семинара.: Воронеж: Воронежский государственный педагогический университет, 2017. С. 530–533.
The creation of an effective regular timetable for railway infrastructure provides a number of advantages for both passengers being transported and for staff is involved in the management and maintenance of the network. The for-mation of a regular schedule for it under conditions of variable demand is an ac-tual problem and a rather difficult task. ...
Added: November 21, 2018
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
Zelenova S. A., Zelenov S. V., Proceedings of the Institute for System Programming of the RAS 2017 Vol. 29 No. 6 P. 183–202
In the paper, we address mission critical systems, such as automobile, avionic, mobile robotic, telecommunication, etc. Such systems must meet hard real-time constraints in order to avoid catastrophic consequences. To meet the real-time constraints, strict periodicity is used (i.e. for any periodic task, time between release points is constant). Sensors, actuators and feedback control functions ...
Added: August 11, 2018
Cherkashin Danila, Kulikov A., Andrei Raigorodskii, Discrete Applied Mathematics 2018 Vol. 243 P. 125–131
This paper is devoted to the study of the graph sequence Gn = (Vn, En), where Vn is the set of all vectors v ∈ R n with coordinates in {−1, 0, 1} such that |v| = √ 3 and En consists of all pairs of vertices with scalar product 1. We find the exact ...
Added: August 6, 2018
Zelenov S. V., Зеленова С. А., Программирование 2018 Т. 44 № 3 С. 3–16
A new look at the problem of constructing a scheduler in the case of a group of strictly periodic tasks is proposed. The structure of the system of periods is represented in terms of graph theory. A criterion for the existence of a conflict-free schedule based on this representation is obtained, and generic schemes of ...
Added: March 15, 2018