Physical Sciences and Mathematics Commons^™

A Novel Multithreaded Algorithm For Extracting Maximal Chordal Subgraphs, Mahantesh Halappanavar, John Feo, Kathryn Dempsey Cooper, Hesham Ali, Sanjukta Bhowmick

Interdisciplinary Informatics Faculty Proceedings & Presentations

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 …