Improved Parallel Implementations of Gusfield´s Cut Tree Algorithm

Summary form only given. This work presents parallel versions of Gusfield´s cut tree algorithm and the proposal of two heuristics aimed at improving their performance. Cut trees are a compact representation of the edge-connectivity between every pair of vertices of an undirected graph. Cut trees have a vast number of applications in combinatorial optimization and in the analysis of networks originated in many applied fields. However, surprisingly few works have been published on the practical performance of cut tree algorithms. This paper describes two parallel versions of Gusfield´s cut tree algorithm and presents extensive experimental results which show a significant speedup on most real and synthetic graphs in our dataset.