Vylepšené algoritmy pro distribuovanou dekompozici grafu na silně souvislé komponenty
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F07%3A00019458" target="_blank" >RIV/00216224:14330/07:00019458 - isvavai.cz</a>
Výsledek na webu
—
DOI - Digital Object Identifier
—
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Improved Distributed Algorithms for SCC Decomposition
Popis výsledku v původním jazyce
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 realmodel checking applications. The experimental results are compared with that of other successful SCC decomposition techniques.
Název v anglickém jazyce
Improved Distributed Algorithms for SCC Decomposition
Popis výsledku anglicky
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 realmodel checking applications. The experimental results are compared with that of other successful SCC decomposition techniques.
Klasifikace
Druh
J<sub>x</sub> - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
CEP obor
IN - Informatika
OECD FORD obor
—
Návaznosti výsledku
Projekt
Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)
Ostatní
Rok uplatnění
2007
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název periodika
CTIT Workshop Proceedings
ISSN
0929-0672
e-ISSN
—
Svazek periodika
2007
Číslo periodika v rámci svazku
WP 07-04
Stát vydavatele periodika
DE - Spolková republika Německo
Počet stran výsledku
16
Strana od-do
65-80
Kód UT WoS článku
—
EID výsledku v databázi Scopus
—