Библиографическое описание:О иерархическом представлении графа для задачи о кратчайшем пути : доклад, тезисы доклада / М. В. Громова, А. А. Солдатенко. - [Б. м. : б. и.], 2025. - Текст : непосредственный // ИТ. Наука. Креатив : Материалы II Международного форума. В 5-ти томах / ИТ. Наука. Креатив (2025 ; 13.05 - 15.05 ; Омск). - Омск, 2025. - С. 294-301. - ISBN 9785814939951.
Аннотация:В работе предложен новый алгоритм иерархического представления графа, основанный на комбинации алгоритмов выделения сообществ в графе и атаки на целостности графа. Иерархическое представление является важным направлением в теории графов, поскольку позволяет эффективно представлять исходный граф в виде нескольких уровней, что позволяет применять оптимизационные алгоритмы не ко всему графу, а лишь к его части, расширяя граф по необходимости. В частности, в задаче о кратчайшем пути методы иерархического представления занимаю важное место в двухфазных подходах решения. Новый алгоритм представлен в виде описания основных шагов. Для демонстрации алгоритма были проведены вычислительные эксперименты на синтетических и реальных данных.
In this paper, we propose a new algorithm for hierarchical graph representation based on a combination of community selection in the graph and graph integrity attack algorithms. Hierarchical representation is an important direction in graph theory because it allows us to efficiently represent the original graph as multiple levels, which allows us to apply optimization algorithms not to the entire graph but only to a part of it, expanding the graph as needed. In particular, in the shortest path problem, hierarchical representation methods occupy an important place in twophase solution approaches. The new algorithm is presented as a description of the main steps. Computational experiments on synthetic and real data were performed to demonstrate the algorithm.
