Тип публикации: доклад, тезисы доклада, статья из сборника материалов конференций
Конференция: ИТ. Наука. Креатив; Омск; Омск
Год издания: 2026
Ключевые слова: shortest path, hierarchical representation, graph theory, algorithmization, graph modularity, кратчайший путь, иерархическое представление, теория графов, алгоритмизация, модулярность графа
Аннотация: В работе приводятся сравнительные эксперименты нового алгоритма иерархического представления графа для задачи о кратчайшем пути, основанный на комбинации алгоритмов выделения сообществ в графе и атаки на целостности графа, с классическими алгоритмами кратчайшего пути. Иерархическое представление является важным направлением в теориПоказать полностьюи графов, поскольку позволяет эффективно представлять исходный граф в виде нескольких уровней, что позволяет применять оптимизационные алгоритмы не ко всему графу, а лишь к его части, расширяя граф по необходимости. В частности, в задаче о кратчайшем пути методы иерархического представления занимают важное место в двухфазных подходах решения. Новый алгоритм представлен в виде описания основных шагов. Для демонстрации алгоритма были проведены вычислительные эксперименты на синтетических и реальных данных. The paper presents comparative experiments of a new algorithm for hierarchical graph representation for the shortest path problem, based on a combination of graph community detection algorithms and graph integrity attacks, with classical shortest path algorithms. Hierarchical representation is an important direction in graph theory, as it allows the original graph to be efficiently represented in several levels, enabling optimization algorithms to operate not on the entire graph but only on a part of it, expanding the graph as needed. In particular, in the shortest path problem, hierarchical representation methods occupy an important place in two-phase solution approaches. The new algorithm is presented as a description of the main steps. To demonstrate the algorithm, computational experiments were conducted on synthetic and real-world data.
Журнал: ИТ. Наука. Креатив
Номера страниц: 153-156
Место издания: Омск