A novel multithreaded algorithm for extracting maximal chordal subgraphs

Mahantesh Halappanavar, John Feo, Kathryn Dempsey, Hesham Ali, Sanjukta Bhowmick

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

4 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings - 41st International Conference on Parallel Processing, ICPP 2012
Pages58-67
Number of pages10
DOIs
StatePublished - 2012
Event41st International Conference on Parallel Processing, ICPP 2012 - Pittsburgh, PA, United States
Duration: Sep 10 2012Sep 13 2012

Publication series

NameProceedings of the International Conference on Parallel Processing
ISSN (Print)0190-3918

Conference

Conference41st International Conference on Parallel Processing, ICPP 2012
Country/TerritoryUnited States
CityPittsburgh, PA
Period9/10/129/13/12

Keywords

  • chordal graphs
  • large scale networks
  • multithreaded algorithms

ASJC Scopus subject areas

  • Software
  • General Mathematics
  • Hardware and Architecture

Fingerprint

Dive into the research topics of 'A novel multithreaded algorithm for extracting maximal chordal subgraphs'. Together they form a unique fingerprint.

Cite this