Vylepšené algoritmy pro distribuovanou dekompozici grafu na silně souvislé komponenty

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F08%3A00024165" target="_blank" >RIV/00216224:14330/08:00024165 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

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.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

IN - Informatika

OECD FORD obor

—

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)

Rok uplatnění

2008

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ů

Název periodika

Electronic Notes in Theoretical Computer Science

ISSN

1571-0661

e-ISSN

—

Svazek periodika

2008

Číslo periodika v rámci svazku

198(1)

Stát vydavatele periodika

DE - Spolková republika Německo

Počet stran výsledku

15

Strana od-do

—

Kód UT WoS článku

—

EID výsledku v databázi Scopus

—