Gathering information in a graph

?

Gathering information in a graph

Journal of Combinatorial Mathematics and Combinatorial Computing. 2013. Vol. 85. P. 65–78.

Beaudou L., Grappe R., Hahn G.

Suppose each vertex in a graph G has a unit of information and that all the units must be collected at a vertex u in G. Assuming that a vertex can receive (from its neighbours) an unlimited number of units at each discrete moment but can only send one at a time, find the shortest collection time, col u(G), needed to collect all the information at u and an optimal protocol that achieves this. We derive lower and upper bounds for the problem, give a polynomial time algorithm in the general case, and a linear time algorithm for hypercubes.

Priority areas: IT and mathematics

Language: English

On calibration of remote sensing retrievals of ecosystem respiration (Reco) with tower measurements over,Russian forests and wetlands

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

Three Algorithms for Merging Hierarchical Navigable Small World 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

Growth in noncommutative algebras and entropy in derived categories

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

Multilinear nilalgebras and the Jacobian theorem

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

ML-based Fast Simulation of FARICH Responses

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

Natural hazard database from Internet publications: text mining with a large language model

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

Algorithmic overlaps as thermodynamic variables: from local to cluster Monte Carlo dynamics in critical phenomena

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

Using predefined vector systems to speed up neural network multimillion class classification

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

Iterative Ricci-Foster Curvature Flow with GMM-Based Edge Pruning: A Novel Approach to Community Detection

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

Implementing Transport Coding in OMNeT++ for Message Delay Reduction

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

Нарушения распознавания когнитивных ошибок другого человека больными шизофренией при восприятии коммуникативных ситуаций

Белоусова А. Ю., Зотова Н. Е., Korotkova I., Вестник психотерапии 2025 № 93 С. 100–112

Relevance. Social cognition impairments in patients with schizophrenia complicate their interactions with others, adversely impacting daily functioning and the progression of the disease. Investigating these impairments is crucial for developing effective strategies for diagnosis, rehabilitation, and psychological intervention to improve patients’ quality of life. Intention. To investigate the impairments in cognitive information processing in patients with ...

Added: April 7, 2025

Modeling of Interaction in Command-information Systems with Dynamic Replicas

Kochkarov A. A., Malinetskii G. G., D.V. Yatskin, , in: Procedia Computer Science Proceedings of the 13th International Symposium "Intelligent Systems", INTELS 2018.: [б.и.], 2019. P. 726–729.

In this paper we introduce an approach to describing the interaction of subscribers - carriers of sensors in information and reconnaissance systems. The approach is based on the use of a special class of graphs – dynamic graphs, defined as a sequence of "classical" static graphs, the transition between which is carried out by various graph ...

Added: March 7, 2025

Determination of solutions for chorus excitation mechanism characteristic equation by means of Van Allen Probe data analysis

Bespalov P. A., Olga N. Savina, Gleb M. Neshchetkin, Advances in Space Research 2024 Vol. 74 P. 6264–6276

In this paper, we focus on studying the quantitative characteristics of the excitation mechanism of chorus emissions closely related to the problem of relativistic electron flux formation in the radiation belts. The study is based on the processing of information accumulated by the Van Allen Probe spacecraft through the analysis of high-resolution data. We have ...

Added: December 13, 2024

New Working Memory Paradigm for Neuroimaging Testing of Visual and Verbal Modality under Different Attentional Involvement

Nikita Otstavnov, Ekaterina Voevodina, Semyon Mening et al., Psychology. Journal of the Higher School of Economics 2024 No. 3 P. 456–471

Working memory (WM) is a cognitive function essential for short-term maintenance of information in a highly accessible state to support goal-directed behavior. The classical behavioral model of WM includes a visuospatial sketchpad, a phonological loop and the central executive. Neuroimaging studies selectively targeted the activity associated with maintenance and processing of modality specific information. However, an experimental design is still missing that would ...

Added: September 19, 2024

Perturbation Analysis of Centrality Measures

Meshcheryakova N., Швыдун С. В., , in: 2023 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM).: IEEE, 2023. P. 407–414.

In recent decades, a large number of centrality measures have been proposed to assess the importance of nodes in complex networks. The choice of the most appropriate centrality index for specific applications is one of the biggest challenges. This paper performs the perturbation analysis of 8 centrality measures. Since most real networks are incomplete and ...

Added: November 4, 2023

Предпосылки для прогнозирования новых направлений движения инвестиционного капитала на основе анализа международных наукометрических баз данных

Semenova A., В кн.: Системный анализ в проектировании и управлении. Сборник научных трудов XXV Международной научной и учебно-практической конференцииЧ. 3.: СПб.: Политех-Пресс, 2021.

This paper proposes the problem statement of forecasting new directions of investment capital movement based on the analysis of information contained in international scientometric databases. The sufficiency of the prerequisites for this problem solution is discussed at the current level of development of related information databases and tools for collection and analysis of quantitative information ...

Added: February 7, 2023

Novel metaphor recognition in L1 and L2 as mediated by syntactic foregrounding: an eye movement study

Rzheshevskaya A. A., Izmalkova A., Вопросы когнитивной лингвистики (Российская Федерация) 2022 No. 4 P. 83–91

The study explores gaze behavior in novel metaphor recognition in L1 and L2 as affected by the syntactic position of a metaphor; therefore, we test the contrastive role of syntactic foregrounding in information processing. Following cognitive linguistic theories of foregrounding [Talmy 2000; Iriskhanova 2014], we expect its effects on both gaze behavior and metaphor recognition ...

Added: December 8, 2022

Explaining the IT Value Through the Information Support of Decision-Making

Zelenkov Y., , in: Digitalization of Society, Economics and Management: A Digital Strategy Based on Post-pandemic DevelopmentsIssue 53.: Springer, 2022. P. 29–48.

Added: April 18, 2022

Transfer Policy and Football Club Performance: Evidence from Network Analysis

Coates D. C., Naidenova I. N., Parshakov P., International Journal of Sport Finance 2020 Vol. 15 No. 3 P. 95–109

This study considers the football transfer market as a network and analyzes how characteristics of a football club’s player transfer network activities influence club performance. We use data on 23,220 unique football clubs from 189countries from 1996 through 2016. Our results show that for sport performance the best strategy is to have well-established relations with ...

Added: August 26, 2020

Information Processing and Management of Uncertainty in Knowledge-Based Systems. IPMU 2020

Cham: Springer, 2020.

We are very pleased to present you with the proceedings of the 18th International Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems (IPMU 2020), held during June 15–19, 2020. The conference was scheduled to take place in Lisbon, Portugal, at the Instituto Superior Técnico, University of Lisbon, located in a vibrant renovated ...

Added: July 8, 2020

A User-Friendly Algorithm for Detecting the Influence of Background Risks on a Model

Gribkova N., Zitikis R., Risks 2018 Vol. 6 No. 3 P. 1–11

Background, or systematic, risks are integral parts of many systems and models in insurance and finance. These risks can, for example, be economic in nature, or they can carry more technical connotations, such as errors or intrusions, which could be intentional or unintentional. A most natural question arises from the practical point of view: is ...

Added: February 28, 2020

Networks Structure, Equilibria, and Adjustment Dynamics in Network Games with Nonhomogeneous Players

Гармаш М. В., Уткина А. А., Korolev A. V., , in: Contributions to Game Theory and Management Volume XIIVol. XII.: ., 2019. P. 128–139.

In this paper, we consider the following problem - what affects the Nash equilibrium amount of investment in knowledge when some agents of the complete graph enter another full one. The solution of this problem will allow us to understand exactly how game agents will behave when deciding whether to enter the other net, what conditions and externalities affect it and ...

Added: September 29, 2019

Contributions to Game Theory and Management Volume XII

., 2019.

Added: September 29, 2019