Skip navigation
Please use this identifier to cite or link to this item: https://libeldoc.bsuir.by/handle/123456789/54859
Full metadata record
DC FieldValueLanguage
dc.contributor.authorPrihozhy, А. А.-
dc.contributor.authorKarasik, O. N.-
dc.coverage.spatialМинскen_US
dc.date.accessioned2024-03-20T12:52:34Z-
dc.date.available2024-03-20T12:52:34Z-
dc.date.issued2024-
dc.identifier.citationPrihozhy, А. А. Blocked algorithm of shortest paths search in sparse graphs partitioned into unequally sized clusters = Блочный алгоритм поиска кратчайших путей в разреженных графах, разбитых на кластеры неравного размера / А. А. Prihozhy, O. N. Karasik // BIG DATA и анализ высокого уровня = BIG DATA and Advanced Analytics : сборник научных статей X Международной научно-практической конференции, Минск, 13 марта 2024 г. : в 2 ч. Ч. 2 / Белорусский государственный университет информатики и радиоэлектроники ; редкол.: В. А. Богуш [и др.]. – Минск, 2024. – С. 262–271.en_US
dc.identifier.urihttps://libeldoc.bsuir.by/handle/123456789/54859-
dc.description.abstractIn this paper we consider the problem of searching shortest paths between all pairs of vertices of a directed weighted sparse graph which is partitioned into clusters by finding dense weakly connected subgraphs. We address this problem by developing new block-based algorithms that describe the shortest paths by matrices of blocks of unequal sizes corresponding to the sizes of the graph clusters. These algorithms extend the capabilities of known existing algorithms using blocks of equal size (such as the blocked algorithms of Floyd-Warshall family) with respect to adequate graph modeling of real networks of dif erent purposes, and with respect to ef icient use of parallelism and computational resources of multiprocessor systems and multi-core processors. The blocked algorithm of finding shortest paths in sparse large size graphs partitioned into clusters that is proposed in this paper reduces, on the one hand, the amount of memory used, and, on the other hand, reduces the number of block recalculations. Diagonal blocks describe shortest paths within clusters, non-diagonal compact blocks describe non numerous weighted arcs connecting clusters. Shortest paths between vertices of dif erent clusters are computed in real time. The memory consumption is reduced compared to the Floyd-Warshall algorithm to a number of times equal to the number of clusters. In order to reduce the number of block recalculations, a new operation is introduced to accurately compute the shortest path between vertices of one cluster, passing through the vertices and edges of another cluster, as well as through the edges connecting the clusters. Applying this operation alone allows us to find solutions that introduce a small error (a few percent) in the lengths of the shortest paths when the weights of edges between clusters are small, and allows us to find exact solutions when the weights of these edges are increased. Accurate solutions can be obtained for sparse graphs modeling road, computer, and other networks.en_US
dc.language.isoenen_US
dc.publisherБГУИРen_US
dc.subjectматериалы конференцийen_US
dc.subjectheterogeneous systemsen_US
dc.subjectclustersen_US
dc.subjectAPSP problemen_US
dc.titleBlocked algorithm of shortest paths search in sparse graphs partitioned into unequally sized clustersen_US
dc.title.alternativeБлочный алгоритм поиска кратчайших путей в разреженных графах, разбитых на кластеры неравного размераen_US
dc.typeArticleen_US
local.description.annotationВ данной статье рассматривается задача поиска кратчайших путей между всеми парами вершин ориентированного взвешенного разреженного графа, который разбит на кластеры путем нахождения плотных слабосвязных подграфов. Мы решаем эту задачу, разрабатывая новые блочные алгоритмы, которые описывают кратчайшие пути матрицами блоков неравных размеров, соответствующих размерам кластеров графа. Эти алгоритмы расширяют возможности известных существующих алгоритмов, использующих блоки одинакового размера (таких как блочный алгоритм Флойда-Уоршелла) в части адекватного моделирования графов реальных сетей различного назначения, а также в части эффективного использования параллелизма и вычислительных ресурсов многопроцессорных систем и многоядерных процессоров. Предлагаемый в данной статье блочный алгоритм поиска кратчайших путей в разреженных графах большого размера, разбитых на кластеры, позволяет, с одной стороны, сократить объем используемой памяти, а с другой – уменьшить количество пересчетов блоков. Диагональные блоки описывают кратчайшие пути внутри кластеров, недиагональные блоки описывают немногочисленные взвешенные дуги, соединяющие кластеры. Кратчайшие пути между вершинами разных кластеров вычисляются в реальном времени. Потребление памяти по сравнению с алгоритмами семейства Флойда-Уоршелла уменьшается в число раз, равное количеству кластеров. Чтобы уменьшить количество пересчетов блоков, нами предложена новая операция, позволяющая точно вычислить кратчайшие пути между вершинами одного кластера, проходящие через вершины и ребра другого кластера, а также через ребра, соединяющие кластеры. Применение только этой операции позволяет построить алгоритмы, которые находят решения, вносящие небольшую ошибку (несколько процентов) в длины кратчайших путей при малых весах ребер между кластерами, и позволяет находить точные решения при увеличении весов этих ребер. Точные решения могут быть получены для разреженных графов, моделирующих дорожные, компьютерные и другие сети.en_US
Appears in Collections:BIG DATA and Advanced Analytics = BIG DATA и анализ высокого уровня : сборник научных статей : в 2 ч. (2024)

Files in This Item:
File Description SizeFormat 
Prihozhy_Blocked_algoritm.pdf1.46 MBAdobe PDFView/Open
Show simple item record Google Scholar

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.