Title :
A Simple Parallel Algorithm for Biconnected Components in Sparse Graphs
Author :
Meher Chaitanya;Kishore Kothapalli
Author_Institution :
Int. Inst. of Inf. Technol., Hyderabad, India
fDate :
5/1/2015 12:00:00 AM
Abstract :
In this paper we design and implement an algorithm for finding the biconnected components of a given graph. Our algorithm is based on experimental evidence that finding the bridges of a graph is usually easier and faster in the parallel setting. We use this property to first decompose the graph into independent and maximal 2-edge-connected sub graphs. To identify the articulation points in these 2-edge connected sub graphs, we again convert this into a problem of finding the bridges on an auxiliary graph. It is interesting to note that during the conversion process, the size of the graph may increase. However, we show that this small increase in size and the run time is offset by the consideration that finding bridges is easier in a parallel setting. We implement our algorithm on an Intel i7 980X CPU running 12 threads. We show that our algorithm is on average 2.45x faster than the best known current algorithms implemented on the same platform.
Keywords :
"Bridges","Algorithm design and analysis","Parallel algorithms","Program processors","Vegetation","Rail to rail inputs","Robustness"
Conference_Titel :
Parallel and Distributed Processing Symposium Workshop (IPDPSW), 2015 IEEE International
DOI :
10.1109/IPDPSW.2015.31