@inproceedings{7d128736409146d59217848b935c7acc,
title = "GPU-based graph decomposition into strongly connected and maximal end components",
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.",
author = "D. Bosnacki and J.P. Katoen and A.J. Wijs",
year = "2014",
doi = "10.1007/978-3-319-08867-9_20",
language = "English",
isbn = "978-3-319-08866-2",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "310--326",
editor = "A. Biere and R. Bloem",
booktitle = "Computer Aided Verification (26th International Conference, CAV 2014, Vienna, Austria, July 18-22, 2014. Proceedings)",
address = "Germany",
note = "conference; 26th International Conference on Computer Aided Verification; 2014-07-18; 2014-07-22 ; Conference date: 18-07-2014 Through 22-07-2014",
}