Improved Distributed Algorithms for SCC Decomposition

被引：9

作者：

Barnat, Jiri ^{[1
]}

Chaloupka, Jakub ^{[1
]}

van de Pol, Jaco ^{[2
]}

机构：

[1] Masaryk Univ, Fac Informat, Brno, Czech Republic

[2] Ctr Wiskunde & Informat, Amsterdam, Netherlands

来源：

ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE | 2008年 / 198卷 / 01期

关键词：

SCC decomposition; parallel; OBF technique;

D O I：

10.1016/j.entcs.2008.02.001

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We study and improve the OBF technique [1], which was used in distributed algorithms for the decomposition of a partitioned graph into its strongly connected components. In particular, we introduce a recursive variant of OBF and experimentally evaluate several different implementations of it that vary in the degree of parallelism. For the evaluation we used synthetic graphs with a few large components and graphs with many small components. We also experimented with graphs that arise as state spaces in real model checking applications. The experimental results are compared with that of other successful SCC decomposition techniques [6,5].

引用

页码：63 / 77

页数：15