| BARNAT, Jiří, Jakub CHALOUPKA a Jaco VAN DE POL. Improved Distributed Algorithms for SCC Decomposition. Electronic Notes in Theoretical Computer Science. Elsevier, 2008, roč. 2008, 198(1), s. 63-77. ISSN 1571-0661. |
Další formáty:
BibTeX
LaTeX
RIS
@article{760854,
author = {Barnat, Jiří and Chaloupka, Jakub and van de Pol, Jaco},
article_number = {198(1)},
keywords = {SCC decomposition; parallel; distributed; OBF},
language = {eng},
issn = {1571-0661},
journal = {Electronic Notes in Theoretical Computer Science},
title = {Improved Distributed Algorithms for SCC Decomposition},
volume = {2008},
year = {2008}
}
TY - JOUR
ID - 760854
AU - Barnat, Jiří - Chaloupka, Jakub - van de Pol, Jaco
PY - 2008
TI - Improved Distributed Algorithms for SCC Decomposition
JF - Electronic Notes in Theoretical Computer Science
VL - 2008
IS - 198(1)
SP - 63-77
EP - 63-77
PB - Elsevier
SN - 15710661
KW - SCC decomposition
KW - parallel
KW - distributed
KW - OBF
N2 - We study and improve the OBF technique, 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.
ER -
BARNAT, Jiří, Jakub CHALOUPKA a Jaco VAN DE POL. Improved Distributed Algorithms for SCC Decomposition. \textit{Electronic Notes in Theoretical Computer Science}. Elsevier, 2008, roč.~2008, 198(1), s.~63-77. ISSN~1571-0661.
|
