Name
Title | ||
|---|---|---|
Efficient GPU algorithms for parallel decomposition of graphs into strongly connected and maximal end components. |
Abstract | ||
|---|---|---|
This article 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 graphs induced by 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 (as well as existing parallel) counterparts in several case studies. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1007/s10703-016-0246-7 | Formal Methods in System Design |
Keywords | Field | DocType |
Parallel graph algorithms,Strongly connected components,Maximal end components,Probabilistic model checking,Markov decision processes,GPU | Graphics,Graph,Modular decomposition,General purpose,Computer science,Parallel algorithm,Algorithm,Markov decision process,Theoretical computer science,Probabilistic logic,Strongly connected component | Journal |
Volume | Issue | ISSN |
48 | 3 | 0925-9856 |
Citations | PageRank | References |
2 | 0.40 | 27 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Anton Wijs | 1 | 203 | 22.84 |
| Joost-Pieter Katoen | 2 | 4444 | 289.65 |
| Dragan Bosnacki | 3 | 276 | 26.95 |