TY - GEN
T1 - A novel multithreaded algorithm for extracting maximal chordal subgraphs
AU - Halappanavar, Mahantesh
AU - Feo, John
AU - Dempsey, Kathryn
AU - Ali, Hesham
AU - Bhowmick, Sanjukta
PY - 2012
Y1 - 2012
N2 - Chordal graphs are triangulated graphs where any cycle larger than three is bisected by a chord. Many combinatorial optimization problems such as computing the size of the maximum clique and the chromatic number are NP-hard on general graphs but have polynomial time solutions on chordal graphs. In this paper, we present a novel multithreaded algorithm to extract a maximal chordal sub graph from a general graph. We develop an iterative approach where each thread can asynchronously update a subset of edges that are dynamically assigned to it per iteration and implement our algorithm on two different multithreaded architectures - Cray XMT, a massively multithreaded platform, and AMD Magny-Cours, a shared memory multicore platform. In addition to the proof of correctness, we present the performance of our algorithm using a test set of synthetical graphs with up to half-a-billion edges and real world networks from gene correlation studies and demonstrate that our algorithm achieves high scalability for all inputs on both types of architectures.
AB - Chordal graphs are triangulated graphs where any cycle larger than three is bisected by a chord. Many combinatorial optimization problems such as computing the size of the maximum clique and the chromatic number are NP-hard on general graphs but have polynomial time solutions on chordal graphs. In this paper, we present a novel multithreaded algorithm to extract a maximal chordal sub graph from a general graph. We develop an iterative approach where each thread can asynchronously update a subset of edges that are dynamically assigned to it per iteration and implement our algorithm on two different multithreaded architectures - Cray XMT, a massively multithreaded platform, and AMD Magny-Cours, a shared memory multicore platform. In addition to the proof of correctness, we present the performance of our algorithm using a test set of synthetical graphs with up to half-a-billion edges and real world networks from gene correlation studies and demonstrate that our algorithm achieves high scalability for all inputs on both types of architectures.
KW - chordal graphs
KW - large scale networks
KW - multithreaded algorithms
UR - http://www.scopus.com/inward/record.url?scp=84871155052&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84871155052&partnerID=8YFLogxK
U2 - 10.1109/ICPP.2012.10
DO - 10.1109/ICPP.2012.10
M3 - Conference contribution
AN - SCOPUS:84871155052
SN - 9780769547961
T3 - Proceedings of the International Conference on Parallel Processing
SP - 58
EP - 67
BT - Proceedings - 41st International Conference on Parallel Processing, ICPP 2012
T2 - 41st International Conference on Parallel Processing, ICPP 2012
Y2 - 10 September 2012 through 13 September 2012
ER -