Concurrent Depth-First Search Algorithms
Concurrent Depth-First Search Algorithms
复制标题
DOI：
10.1007/978-3-642-54862-8_14
复制
发表时间：
2014-04
期刊：
影响因子：
--
通讯作者：
G. Lowe
中科院分区：
文献类型：
--
作者：
G. Lowe
我们提出了并发算法，深度优先搜索的基础上，三个问题相关的模型检查：给定一个状态图，找到其强连接的组件，其中状态是在循环中，以及哪些状态是在“套索”。我们的算法通常表现出约四倍的速度比相应的顺序算法在八核机器。
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”. Our algorithms typically exhibit about a four-fold speed-up over the corresponding sequential algorithms on an eight-core machine.