Simple parallel biconnectivity algorithms for multicore platforms

George M. Slota, Kamesh Madduri

Research output: Chapter in Book/Report/Conference proceedingConference contribution

23 Scopus citations

Abstract

We present two new algorithms for finding the biconnected components of a large undirected sparse graph. The first algorithm is based on identifying articulation points and labeling edges using multiple connectivity queries, and the second approach uses the color propagation technique to decompose the graph. Both methods use a breadth-first spanning tree and some auxiliary information computed during Breadth-First Search (BFS). These methods are simpler than the Tarjan-Vishkin PRAM algorithm for biconnectivity and do not require Euler tour computation or any auxiliary graph construction. We identify steps in these algorithms that can be parallelized in a shared-memory environment and develop tuned OpenMP implementations. Using a collection of large-scale real-world graph instances, we show that these methods outperform the state-of-the-art Cong-Bader biconnected components implementation, which is based on the Tarjan-Vishkin algorithm. We achieve up to 7.1× and 4.2× parallel speedup over the serial Hopcroft-Tarjan and parallel Cong-Bader algorithms, respectively, on a 16-core Intel Sandy Bridge system. For some graph instances, due to the fast BFS-based preprocessing step, the single-threaded implementation of our first algorithm is faster than the serial Hopcroft-Tarjan algorithm.

Original languageEnglish (US)
Title of host publication2014 21st International Conference on High Performance Computing, HiPC 2014
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781479959761
DOIs
StatePublished - 2014
Event2014 21st International Conference on High Performance Computing, HiPC 2014 - Goa, India
Duration: Dec 17 2014Dec 20 2014

Publication series

Name2014 21st International Conference on High Performance Computing, HiPC 2014

Other

Other2014 21st International Conference on High Performance Computing, HiPC 2014
Country/TerritoryIndia
CityGoa
Period12/17/1412/20/14

All Science Journal Classification (ASJC) codes

  • Computer Science (miscellaneous)
  • Hardware and Architecture
  • Software

Fingerprint

Dive into the research topics of 'Simple parallel biconnectivity algorithms for multicore platforms'. Together they form a unique fingerprint.

Cite this