GPU-based graph decomposition into strongly connected and maximal end components

D. Bosnacki, J.P. Katoen, A.J. Wijs

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

9 Citations (Scopus)
4 Downloads (Pure)

Abstract

This paper presents parallel algorithms for component decomposition of graph structures on General Purpose Graphics Processing Units (GPUs). In particular, we consider the problem of decomposing sparse graphs into strongly connected components, and decomposing stochastic games (such as Markov decision processes) into maximal end components. These problems are key ingredients of many (probabilistic) model-checking algorithms. We explain the main rationales behind our GPU-algorithms, and show a significant speed-up over the sequential counterparts in several case studies.
Original languageEnglish
Title of host publicationComputer Aided Verification (26th International Conference, CAV 2014, Vienna, Austria, July 18-22, 2014. Proceedings)
EditorsA. Biere, R. Bloem
Place of PublicationBerlin
PublisherSpringer
Pages310-326
ISBN (Print)978-3-319-08866-2
DOIs
Publication statusPublished - 2014
Eventconference; 26th International Conference on Computer Aided Verification; 2014-07-18; 2014-07-22 -
Duration: 18 Jul 201422 Jul 2014

Publication series

NameLecture Notes in Computer Science
Volume8559
ISSN (Print)0302-9743

Conference

Conferenceconference; 26th International Conference on Computer Aided Verification; 2014-07-18; 2014-07-22
Period18/07/1422/07/14
Other26th International Conference on Computer Aided Verification

Fingerprint Dive into the research topics of 'GPU-based graph decomposition into strongly connected and maximal end components'. Together they form a unique fingerprint.

Cite this