?
Encoding partial orders through modular decomposition.
Journal of Computational Science. 2018. Vol. 25. P. 446–455.
Beaudou L., Ghazi K., Kahn G., Raynaud O., Thierry É.
Let P be a poset and S be a set of elements. A well-known method for representing P is called a bit-vector encoding and consists in associating to each element of P a subset of S such that the order relation between two elements coincides with their subsets inclusion. The size of this encoding is |S| and it determines both space and time needed to store and compare the poset's elements. As a consequence, this encoding has found applications for handling hierarchies in databases, distributed computing, object-oriented programming languages, etc. The computation of the smallest size of a bit-vector encoding of a poset, called the 2-dimension, is an -hard problem. Thus, researches deal with heuristics that provide tight bounds or an approximation of this parameter. Our paper introduces new classes of trees whose the 2-dimension is either known or 2-approximated. Moreover, it presents a new heuristic for partial orders encoding through the modular decomposition. This unified process is a 4-approximation for the 2-dimension of rooted trees and provides reduced encoding by almost 40% for series-parallel posets. It reaches or improves the best results for general posets.
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
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
D'yakonov A., Штыков П. А., Прикладная дискретная математика 2023 № 59 С. 111–127
We propose a definition of a generalized dialog graph, which is used to describe the structure of a dialog over a corpus of homogeneous dialogs. The task of constructing such a graph is relevant in modern conversational artificial intelligence, but there are few works with specific results, often no full description of algorithms is given, ...
Added: March 18, 2024
Sidorov Nikita, Slastnikov Sergey, Journal of Physics: Conference Series 2021 Vol. 1740 P. 1–6
Sentiment analysis of different language texts is one of the very popular machine learning tasks. The complexity of its solution depends both on the characteristics of a particular language, and on the length of the evaluated texts. In our work, we consider the task of creating a sentiment analysis software tool for Russian posts and ...
Added: February 2, 2021
Scherbakova A., / NRU HSE. Series WP BRP "Linguistics". 2020.
Added: December 2, 2020
Utkina I. E., , in: Computational Aspects and Applications in Large-Scale Networks. Springer Proceedings in Mathematics & StatisticsVol. 247.: Springer, 2018. P. 121–131.
In this article we use the modular decomposition technique for exact solving the weighted maximum clique problem. Our algorithm takes the modular decomposition tree from the paper of Tedder et. al. and finds solution recursively. Also, we propose algorithms to construct graphs with modules. We show some interesting results, comparing our solution with Ostergards algorithm ...
Added: October 18, 2017
Utkina I. E., /. 2017.
In this article we use the modular decomposition technique for exact solving the weighted maximum clique problem. Our algorithm takes the modular decomposition tree from the paper of Tedder et. al. and finds solution recursively. Also, we propose algorithms to construct graphs with modules. We show some interesting results, comparing our solution with Ostergard's algorithm ...
Added: October 15, 2017
Skopenkov M., International Journal of Mathematics 2015 Vol. 26 No. 7, Article number 1550051 P. 1–28
Given a manifold N and a number m, we study the following question: is the set of isotopy classes of embeddings N → Sm finite? In case when the manifold N is a sphere the answer was given by A. Haefliger in 1966. In case when the manifold N is a disjoint union of spheres the ...
Added: September 8, 2015
Cencelj M., Repovs D., Mikhail Skopenkov, Sbornik Mathematics 2012 Vol. 203 No. 11 P. 1654–1681
This paper is on the classical Knotting Problem: for a given manifold N and a number m describe the set of isotopy classes of embeddings N->S^m. We study the specific case of knotted tori, i. e. the embeddings S^p x S^q -> S^m. The classification of knotted tori up to isotopy in the metastable dimension ...
Added: September 26, 2014
Karpenko I., , in: Logical InvestigationsVol. 19: Special Issue.: M., St. Petersburg: humanitarian initiatives center, 2013. P. 308–325.
This article deals with the problem of translations. It covers the history of translation in linguistics and analyzes peculiarities and role of translation in logic. Moreover, the article contains typical examples of embedding operations in terms of dierent logical theories. ...
Added: March 13, 2014
Bogataya S., Bogatyi S., E.A.Kudryavtseva, Sbornik Mathematics 2012 Vol. 203 No. 4 P. 554–568
We prove that the bound from the theorem on 'economic' maps is best possible. Namely, for m > n + d we construct a map from an n-dimensional simplex to an m-dimensional Euclidean space for which (and for any close map) there exists a d-dimensional plane whose preimage has cardinality not less than the upper ...
Added: November 16, 2012
Bogataya S., Bogatyi S., Кудрявцева Е. А., Математический сборник 2012 Т. 203 № 4 С. 103–118
We prove that the bound from the theorem on ‘economic’ maps is best possible. Namely, for m > n + d we construct a map from an n-dimensional simplex to an m-dimensional Euclidean space for which (and for any close map) there exists a d-dimensional plane whose preimage has cardinality not less than the upper ...
Added: October 30, 2012
Cheltsov I., Shramov K., Transformation Groups 2012 Vol. 17 No. 2 P. 303–350
We study the action of the Klein simple group PSL2(F7 ) consisting of 168 elements on two rational threefolds: the three-dimensional projective space and a smooth Fano threefold X of anticanonical degree 22 and index 1. We show that the Cremona group of rank three has at least three non-conjugate subgroups isomorphic to PSL2(F7 ). As a ...
Added: August 30, 2012