?
A fast greedy sequential heuristic for the vertex colouring problem based on bitwise operations
Journal of Combinatorial Optimization. 2016. No. 4. P. 1665–1677.
In this paper a fast greedy sequential heuristic for the vertex colouring problem is presented. The suggested algorithm builds the same colouring of the graph as the well-known greedy sequential heuristic in which on every step the current vertex is coloured in the minimum possible colour. Our main contributions include introduction of a special matrix of forbidden colours and application of efficient bitwise operations on bit representations of the adjacency and forbidden colours matrices. Computational experiments show that in comparison with the classical greedy heuristic the average speedup of the developed approach is 2.6 times on DIMACS instances.
Teregulov T., Loubenets E. R., / Series Quantum Physics "arXiv". 2026. No. 2609.31472.
We develop a new three-party quantum secret-sharing (QSS) protocol based on a three-qubit W state. This protocol encodes the secret-sequence bits using X gates and employs randomly selected Hadamard operations and measurement bases to generate information and security-test rounds. We evaluate the efficiency of the proposed protocol and analyze its security against an internal adversary ...
Added: September 28, 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
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
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
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
Максимова Елизавета Андреевна, В кн.: Системное моделирование социально-экономических процессов: труды 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
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
Зеленова С. А., Zelenov S. V., Труды Института системного программирования РАН 2017 Т. 29 № 6 С. 183–202
В критических системах выполнение жестких требований по времени взаимодействия между задачами обеспечивается строгой периодичностью запуска задач, когда каждая задача стартует через равные промежутки времени. При планировании строго периодических задач с прерываниями наиболее трудным этапом является выбор начальных стартовых точек задач. В настоящей работе предлагается новый подход к анализу расписаний, основанный на изучении раскрасок графов периодов ...
Added: February 12, 2018
Toporkov V., Yemelyanov D., Anna Toporkova, , in: PROCEEDINGS 46th International Conference on Parallel Processing Workshops ICPPW 2017.: Piscataway: IEEE Computer Society, 2017. P. 271–280.
In this work, a job-flow scheduling approach for Grid virtual organizations (VOs) is proposed and studied. Users’ and resource providers’ preferences, VOs internal policies, resources geographical distribution along with local private utilization impose specific requirements for efficient scheduling according to different, usually contradictive, criteria. With increasing resources utilization level the available resources set and corresponding ...
Added: January 30, 2018
Toporkov V., Yemelyanov D., Anna Toporkova, , in: Supercomputing. RuSCDays 2017. Communications in Computer and Information Science. Revised Selected Papers.Vol. 793.: Springer, 2017. P. 482–493.
In this work, a job-flow scheduling approach for grid virtual organizations (VOs) is proposed and studied. Users’ and resource providers’ preferences, VOs internal policies, resources geographical distribution along with local private utilization impose specific requirements for efficient scheduling according to different, usually contradictive, criteria. With increasing level of resources utilization, the set of available resources ...
Added: January 30, 2018
Toporkov V., Yemelyanov D., Anna Toporkova et al., , in: Parallel Computing Technologies. 14th International Conference, PaCT 2017, Nizhny Novgorod, Russia, September 4-8, 2017, ProceedingsVol. 10421: Lecture Notes in Computer Science .: Cham, Switzerland: Springer, 2017. P. 372–383.
In this work, a job-flow scheduling approach for Grid virtual organizations (VOs) is proposed and studied. Users’ and resource providers’ preferences, VOs internal policies, resources geographical distribution along with local private utilization impose specific requirements for efficient scheduling according to different, usually contradictive, criteria. With increasing resources utilization level the available resources set and corresponding ...
Added: January 26, 2018
Shabanov D. A., Доклады Академии наук 2017 Т. 475 № 1 С. 24–28
В работе исследуется проблема нахождения предельного распределения хроматического числа случайного однородного гиперграфа в разреженном случае. Показано, что для большей части значений параметров модели предельное значение хроматического числа концентрируется ровно в одной точке, которая может быть явно вычислена. ...
Added: July 19, 2017