RECONFIGURABLE HETEROGENEOUS BLOCKED SHORTEST PATH ALGORITHM FOR CLUSTERED GRAPHS

Read full text Summarise with VIRAT
Authors: Prihozhy Anatoly Alexievich, Karasik Oleg Nikolaevich
Cited by: 0
References: 11

Summary

No summary yet. VIRAT can read this paper and write a plain-language summary of its aim, methods, key findings and limitations.

Summarise with VIRAT Free to try with your Science Catalogs account.

Abstract

Transportation systems, social networks, network configurations, and many other systems in the surrounding world can be represented by clustered graphs consisting of weakly connected dense clusters. Finding shortest paths in such large-size graphs is a challenging but computationally difficult problem. Heterogeneous block algorithms that utilize information about clusters and the connections between them are a promising approach to solving this problem. The paper develops a new reconfigurable heterogeneous blocked all-pairs shortest paths algorithm for the clustered graphs. The algorithm is based on two new sub-algorithms for calculating cross blocks which account for the reduced communication between clusters and the features of multi-core processors. The paper provides results of two-series experiments, carried out on samples of clustered 9600-vertex graphs at the aim of analysis and comparison of the new algorithm with known techniques. The experiments convincingly demonstrate that the new feature of the algorithm to reconfigure its structure depending on the graph properties provides the speed up from 17.05% to 29.62% in single-threaded and from 5.03% to 14.72% in multi-threaded implementations

Fields of Study & Subjects

Graph Theory and Algorithms Complexity and Algorithms in Graphs Parallel Computing and Optimization Techniques

Publication details

Journal / source
Труды БГТУ. Серия 3: Физико-математические науки и информатика
Publication date
1 January 2026
Language
EN