Concurrent depth-first search algorithms based on Tarjan's Algorithm
2016
We present concurrent algorithms, based on depth-first search, for three problems relevant to model checking: given a state graph, to find its strongly connected components, which states are in loops, and which states are in "lassos". Each algorithm is a variant of Tarjan's Algorithm. Our algorithms typically exhibit a three- or four-fold speed-up over the corresponding sequential algorithms on an eight-core machine.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
25
References
16
Citations
NaN
KQI