Reconfigurable heterogeneous blocked shortest path algorithm for clustered graphs

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