Efficient GPU algorithms for parallel decomposition of graphs into strongly connected and maximal end components

DOI10.1007/s10703-016-0246-7zbMath1404.68204OpenAlexW2323352721WikidataQ57800546 ScholiaQ57800546MaRDI QIDQ518409

Joost-Pieter Katoen, Dragan Bošnački, Anton Wijs

Publication date: 28 March 2017

Published in: Formal Methods in System Design (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10703-016-0246-7

zbMATH Keywords

Markov decision processesGPUprobabilistic model checkingstrongly connected componentsmaximal end componentsparallel graph algorithms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Specification and verification (program logics, model checking, etc.) (68Q60) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Related Items (5)

Symbolic coloured SCC decomposition ⋮ Efficient GPU algorithms for parallel decomposition of graphs into strongly connected and maximal end components ⋮ Unnamed Item ⋮ Finding strongly connected components of simple digraphs based on granulation strategy ⋮ Where is this leading me: stationary point and equilibrium analysis for self-modeling network models

Uses Software

• PRISM
• CUDA
• Easychair
• GPU-PRISM
• GPUexplore

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Efficient GPU algorithms for parallel decomposition of graphs into strongly connected and maximal end components
• Finding strongly connected components in distributed graphs
• An algorithm for strongly connected component analysis in \(n \log n\) symbolic steps
• Compositional SCC analysis for language emptiness
• Meet Your Expectations With Guarantees: Beyond Worst-Case Synthesis in Quantitative Games
• Efficient and Dynamic Algorithms for Alternating Büchi Games and Maximal End-Component Decomposition
• The Complexity of Nash Equilibria in Stochastic Multiplayer Games
• The complexity of probabilistic verification
• Depth-First Search and Linear Graph Algorithms

This page was built for publication: Efficient GPU algorithms for parallel decomposition of graphs into strongly connected and maximal end components