DocumentCode :
3664196
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
fYear :
2015
fDate :
5/1/2015 12:00:00 AM
Firstpage :
395
Lastpage :
404
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"
Publisher :
ieee
Conference_Titel :
Parallel and Distributed Processing Symposium Workshop (IPDPSW), 2015 IEEE International
Type :
conf
DOI :
10.1109/IPDPSW.2015.31
Filename :
7284338
Link To Document :
بازگشت